Skip to content
← Back

src/ir/llvm/llvm_backend.ghul

1
namespace IR.LLVMTarget is
2
use IR.Program
3
4
use IO.File
5
6
use Collections.LIST
7
use Collections.MAP
8
use Collections.STACK
9
use Collections.SET
10
11
use Semantic.Symbols.Symbol
12
use Semantic.Symbols.Classy
13
use Semantic.Symbols.Function
14
15
use LLVM.MODULE
16
use LLVM.FUNCTION
17
use LLVM.PARAMETER
18
use LLVM.WRITER
19
20
use Values.Value
21
22
/// Writes the program as an LLVM module, and links an executable from it
23
/// with `ghul-llvm` against the runtime.
24
///
25
/// A body's lowering needs what only the whole program settles, so each
26
/// body is kept as it is finished and lowered once the last has been
27
/// handed over, in `end_assembly`.
28
class LLVM_BACKEND: Backend is
29
_bodies: MAP[Function, LIST[Value]]
30
_order: LIST[Function]
31
_frame_members: LIST[(frame: Classy, method: Function)]
32
_enclosing: STACK[LIST[Value]?]
33
_current: LIST[Value]?
34
35
_entry_point: Function?
36
_module: MODULE?
37
_want_library: bool
38
_debug_info: LLVM_DEBUG_INFO?
39
_objects: LLVM_OBJECTS?
40
41
// The functions the program's own sources compiled to, for the text
42
// `--llvm-program-only` asks for.
43
_program_functions: SET[FUNCTION]
44
45
init() is
46
_bodies = MAP[Function, LIST[Value]]()
47
_order = LIST[Function]()
48
_frame_members = LIST[(frame: Classy, method: Function)]()
49
_enclosing = STACK[LIST[Value]?]()
50
_program_functions = SET[FUNCTION]()
51
si
52
53
/// Starts a module, discarding anything kept from an earlier one.
54
install(module_name: string, module_version: string, want_library: bool) is
55
reset()
56
57
_want_library = want_library
58
si
59
60
reset() is
61
_bodies.clear()
62
_order.clear()
63
_frame_members.clear()
64
_enclosing.clear()
65
_current = null
66
_entry_point = null
67
_module = null
68
_program_functions.clear()
69
si
70
71
begin_assembly() is si
72
73
/// Lowers every kept body the program reaches into the module `write`
74
/// writes.
75
end_assembly() is
76
_module = _build_module()
77
si
78
79
add_resource(name: string, content: ubyte[]) is si
80
81
/// Writes the module's text to `<path>.ll` and, for an executable,
82
/// links it into `path` with `ghul-llvm`. The text is kept where
83
/// `--llvm-output` names a file for it.
84
write(path: string) is
85
let module = _module
86
87
if !module? then
88
return
89
fi
90
91
let kept = IoC.CONTAINER.instance.build_flags.llvm_output
92
93
// What `--llvm-output` keeps can be the program's functions
94
// alone, while the module linked stays whole.
95
let program_only = IoC.CONTAINER.instance.build_flags.want_llvm_program_only
96
let copy = if program_only then null else kept fi
97
98
if _want_library then
99
_write_text(module, path, copy)
100
_write_program_only(module, kept, program_only)
101
return
102
fi
103
104
// Where only the module's text is wanted, it is all that is
105
// written.
106
if let k = kept /\ IoC.CONTAINER.instance.build_flags.want_llvm_no_link then
107
_write_text(module, k, null)
108
_write_program_only(module, kept, program_only)
109
return
110
fi
111
112
let ll_path = "{path}.ll"
113
114
// The text kept for `--llvm-output` may be the very file the
115
// linker reads, which is then left in place.
116
let is_kept = kept? /\ IO.Path.get_full_path(kept) =~ IO.Path.get_full_path(ll_path)
117
118
_write_text(module, ll_path, copy)
119
120
try
121
LLVM_LINKER.link(ll_path, path, IoC.CONTAINER.instance.build_flags.llvm_optimisation_level)
122
finally
123
if !is_kept then
124
File.delete(ll_path)
125
fi
126
127
_write_program_only(module, kept, program_only)
128
yrt
129
si
130
131
// Writes the program's own functions to `kept` where only those are
132
// to be kept.
133
_write_program_only(module: MODULE, kept: string?, program_only: bool) is
134
if let k = kept /\ program_only then
135
File.write_all_text(k, WRITER.functions_text(module, f => _program_functions.contains(f)))
136
fi
137
si
138
139
// Writes the module's text to `path`, and to `copy` too where that
140
// names another file, a piece at a time as it is written, so the
141
// text of the whole module is never held.
142
_write_text(module: MODULE, path: string, copy: string?) is
143
let writers = LIST[IO.TextWriter]()
144
145
writers.add(IO.File.create_text(path))
146
147
if let c = copy /\ IO.Path.get_full_path(c) !~ IO.Path.get_full_path(path) then
148
writers.add(IO.File.create_text(c))
149
fi
150
151
// Each writer is flushed every megabyte or so rather than every
152
// piece, so what a writer holds stays small without a file
153
// operation for every function.
154
let unflushed mut = 0
155
156
try
157
WRITER.write_module(module, text is
158
for writer in writers do
159
writer.write(text)
160
od
161
162
unflushed = unflushed + text.length
163
164
if unflushed > 1_000_000 then
165
for writer in writers do
166
writer.flush()
167
od
168
169
unflushed = 0
170
fi
171
si)
172
finally
173
for writer in writers do
174
writer.dispose()
175
od
176
yrt
177
si
178
179
begin_body() is
180
_enclosing.push(_current)
181
_current = LIST[Value]()
182
si
183
184
begin_body(member: Symbol) is
185
begin_body()
186
si
187
188
write(value: Value) is
189
_current!.add(value)
190
si
191
192
/// Keeps the body for lowering. A function that provides an intrinsic
193
/// has its body dropped, since a call to it lowers to the operation
194
/// itself, except an array's members, for a call that reaches one
195
/// through a trait, and a constructor intrinsic, which is called as
196
/// the ordinary method it is.
197
finish_body(function: Function) is
198
if let operation = function.intrinsic_operation /\ !(operation.starts_with("array.") /\ function.is_instance) /\ !operation.starts_with("constructor.") then
199
return
200
fi
201
202
if !_bodies.contains_key(function) then
203
_order.add(function)
204
fi
205
206
_bodies[function] = _current!
207
si
208
209
/// Keeps a generator's or an asynchronous function's frame member as
210
/// a method of the frame, which dispatch reaches as it reaches any
211
/// other implementation. A member no trait the frame implements stands
212
/// for is dropped: nothing on this target calls it.
213
finish_frame_member_body(frame: Classy, member: FrameMember) is
214
let method =
215
if let generator: Semantic.Symbols.STATE_MACHINE_FRAME = frame then
216
FRAME_MEMBER_METHODS.method_for(generator, member)
217
elif let asynchronous: Semantic.Symbols.ASYNC_STATE_MACHINE_FRAME = frame then
218
FRAME_MEMBER_METHODS.method_for(asynchronous, member)
219
else
220
null
221
fi
222
223
if let m = method then
224
_frame_members.add((frame, m))
225
_order.add(m)
226
_bodies[m] = _current!
227
fi
228
si
229
230
/// Drops the initializer: a unit variant's one instance is a global
231
/// whose fields are all zero, built where the module is finished.
232
finish_unit_variant_initializer(variant: Classy) is si
233
234
end_body() is
235
assert _enclosing.count > 0 else "body ended without one begun"
236
237
_current = _enclosing.pop()
238
si
239
240
abandon_bodies() is
241
_enclosing.clear()
242
_current = null
243
si
244
245
/// Always false: a unit variant's instance is built by the backend, not
246
/// by an initializer the program runs.
247
has_unit_variant_instance(variant: Classy) -> bool => false
248
249
mark_entry_point(function: Function) is
250
_entry_point = function
251
si
252
253
_report(location: Source.LOCATION, construct: string) is
254
IoC.CONTAINER.instance.logger.error(
255
location,
256
"code generation for {construct} is not supported on the llvm target")
257
si
258
259
// Finds every instance the program reaches through the program plan,
260
// declaring an LLVM function for each the first time it is named,
261
// then lowers each body into its function.
262
_build_module() -> MODULE is
263
let module = MODULE()
264
let names = LLVM_NAMES()
265
266
_debug_info = if IoC.CONTAINER.instance.build_flags.want_debug then LLVM_DEBUG_INFO(module) else null fi
267
268
let worklist = FUNCTION_WORKLIST(f => _bodies.contains_key(f))
269
let declared = MAP[FUNCTION_INSTANCE, FUNCTION?]()
270
271
let declare = (instance: FUNCTION_INSTANCE) -> FUNCTION? is
272
let found: FUNCTION? mut
273
274
if declared.try_get_value(instance, found ref) then
275
return found
276
fi
277
278
let function =
279
if worklist.add(instance)? then
280
_declare(instance, names.name_of(instance))
281
else
282
null
283
fi
284
285
if let declared_function = function /\ PROGRAM_FUNCTIONS.contains(instance.definition) then
286
_program_functions.add(declared_function)
287
fi
288
289
declared[instance] = function
290
291
return function
292
si
293
294
// An executable compiles what its entry point reaches; a library
295
// compiles everything that is not generic, since anything can be
296
// called from outside.
297
if let entry = _entry_point then
298
declare(FUNCTION_INSTANCE.of(entry))
299
300
// The description of an exception nothing caught reads its
301
// message.
302
if let getter = LLVM_EXCEPTIONS.message_getter /\ _bodies.contains_key(getter) then
303
declare(FUNCTION_INSTANCE.of(getter))
304
fi
305
306
// A read through null that faults throws the null-reference
307
// exception, made by its constructor.
308
if let constructor = LLVM_EXCEPTIONS.null_reference_constructor /\ _bodies.contains_key(constructor) then
309
declare(FUNCTION_INSTANCE.of(constructor))
310
fi
311
else
312
for function in _order do
313
if !FUNCTION_BODIES.is_generic(function) then
314
declare(FUNCTION_INSTANCE.of(function))
315
fi
316
od
317
fi
318
319
let container = IoC.CONTAINER.instance
320
let object = cast Classy?(container.innate_symbol_lookup.get_object_type().symbol)
321
let classes = CLASS_SET(object, element => LLVM_ARRAYS.holds_element(element), INNATE_CORE_CLASSES())
322
let objects = LLVM_OBJECTS(module, names, classes, cast Classy?(container.innate_symbol_lookup.get_string_type().symbol))
323
324
_objects = objects
325
326
objects.collect(container.symbol_table.global_scope)
327
328
for (frame, method) in _frame_members do
329
objects.add_method(frame, method)
330
od
331
332
// A boxed enum answers to_string with its member names.
333
for (_, boxed) in classes.boxes do
334
if let `enum: Semantic.Symbols.ENUM_STRUCT = boxed.symbol, (method, body) = ENUM_BOX_METHODS.to_string_for(`enum) then
335
objects.add_method(`enum, method)
336
_bodies[method] = body
337
_order.add(method)
338
fi
339
od
340
341
let display = DISPLAY_PLAN(objects, classes.core)
342
343
let plan =
344
PROGRAM_PLAN(
345
classes,
346
worklist,
347
objects.dispatched,
348
display,
349
_order)
350
351
objects.reach = instance => declare(instance)
352
353
let discovery_module = MODULE()
354
let discovery_strings = LLVM_STRINGS(discovery_module)
355
let discovery_arrays = LLVM_ARRAYS(discovery_module, discovery_strings, classes, objects)
356
357
plan.discover(
358
LLVM_DISCOVERY(
359
objects,
360
instance => _reach(discovery_module, discovery_strings, discovery_arrays, objects, instance, declare),
361
(location, construct) => _report(location, construct)))
362
363
worklist.seal()
364
365
objects.build()
366
objects.exact.solve()
367
368
if let debug_info = _debug_info then
369
debug_info.objects = objects
370
fi
371
372
let strings = LLVM_STRINGS(module, names)
373
let arrays = LLVM_ARRAYS(module, strings, classes, objects)
374
let closures = LLVM_CLOSURES(module, objects)
375
376
objects.closures = closures
377
378
let callee = (instance: FUNCTION_INSTANCE) -> FUNCTION? is
379
let found: FUNCTION? mut
380
381
declared.try_get_value(instance, found ref)
382
383
return found
384
si
385
386
worklist.restart()
387
388
while let instance = worklist.next() do
389
if let function = callee(instance) then
390
if !_want_library then
391
function.linkage = LLVM.Linkage.INTERNAL
392
fi
393
394
module.add_function(function)
395
396
_lower(module, strings, arrays, objects, instance, function, callee)
397
fi
398
od
399
400
LLVM_DISPLAY(module, objects, display, strings, callee).add()
401
402
objects.finish(strings, callee)
403
404
if !objects.has_string_type then
405
strings.add_placeholder_descriptor()
406
fi
407
408
closures.finish(strings, callee)
409
410
for (location, construct) in objects.unsupported do
411
_report(location, construct)
412
od
413
414
if let entry = _entry_point then
415
_add_entry(module, strings, arrays, entry, callee(FUNCTION_INSTANCE.of(entry)))
416
417
strings.add_exports()
418
arrays.add_exports()
419
420
let getter = LLVM_EXCEPTIONS.message_getter
421
422
LLVM_EXCEPTIONS.add_report_unhandled(module, strings, if let g = getter then callee(FUNCTION_INSTANCE.of(g)) else null fi)
423
424
if let c = LLVM_EXCEPTIONS.null_reference_constructor,
425
type = objects.class_of(IR.Program.CORE_LIBRARY.exception_class(Semantic.Lookups.RuntimeException.NULL_REFERENCE)!, MAP[Semantic.Symbols.Symbol, Semantic.Types.Type]()),
426
constructor = callee(FUNCTION_INSTANCE.of(c))
427
then
428
LLVM_EXCEPTIONS.add_make_null_reference(module, strings, objects, type, constructor)
429
fi
430
fi
431
432
_debug_info?.finish()
433
434
return module
435
si
436
437
// Lowers `instance`'s body into a copy of its function in `module`,
438
// which is thrown away, so every instance it calls is declared.
439
_reach(
440
module: MODULE,
441
strings: LLVM_STRINGS,
442
arrays: LLVM_ARRAYS,
443
objects: LLVM_OBJECTS,
444
instance: FUNCTION_INSTANCE,
445
declare: (FUNCTION_INSTANCE) -> FUNCTION?
446
) is
447
// The plan adds implementations a dispatched call can reach without
448
// naming them, so an instance can arrive here undeclared.
449
if let found = declare(instance) then
450
let copy = FUNCTION(found.name, found.result, found.parameters |> Ghul.Pipes.collect())
451
452
LLVM_LOWERING(module, copy, instance, instance.specialize(instance.definition.return_type), declare, strings, arrays, objects)
453
.lower(_bodies[instance.definition])
454
fi
455
si
456
457
/// The name of the function the runtime starts the program at, which
458
/// takes nothing and returns the exit status.
459
ENTRY_NAME: string static => "$ghul_entry"
460
461
/// The global the runtime defines for the ABI version the program is
462
/// compiled for, which a runtime of any other version lacks.
463
ABI_CHECK_NAME: string static => "$ghul_abi_4"
464
465
// Exports `$ghul_entry`, which calls the entry point and returns the
466
// exit status it answers, or zero for an entry point that answers
467
// nothing. An entry point taking a `string[]` is handed the
468
// command-line arguments, read through the runtime's host operations.
469
// It reads the runtime's ABI marker, so a program linked against a
470
// runtime of another ABI version fails to link rather than failing
471
// when it runs.
472
_add_entry(module: MODULE, strings: LLVM_STRINGS, arrays: LLVM_ARRAYS, entry: Function, compiled: FUNCTION?) is
473
let string_array: CLASS_INSTANCE? mut
474
475
if entry.arguments.count == 1 then
476
string_array = arrays.array_of(entry.arguments[0])
477
478
if !string_array? \/ !LLVM_TYPES.is_string(arrays.element_of(string_array)) then
479
_report(entry.location, "an entry point taking {entry.arguments[0]}")
480
return
481
fi
482
elif entry.arguments.count > 1 then
483
_report(entry.location, "an entry point that takes more than one argument")
484
return
485
fi
486
487
if !compiled? then
488
return
489
fi
490
491
let wrapper = FUNCTION(ENTRY_NAME, LLVM.Types.i32, [])
492
let block mut = wrapper.add_block("entry")
493
494
let marker = LLVM.GLOBAL_VARIABLE(ABI_CHECK_NAME, LLVM.Types.i32, null, true)
495
496
module.add_global(marker)
497
498
let read = wrapper.fresh_name()
499
500
block.append(LLVM.Operation.LOAD(read, LLVM.Types.i32, marker.reference, 4, true), LLVM.Values.local(LLVM.Types.i32, read))
501
502
let arguments = LIST[LLVM.Value]()
503
504
if let type = string_array then
505
arguments.add(_command_line(wrapper, block, strings, arrays, type))
506
507
block = wrapper.blocks[wrapper.blocks.count - 1]
508
fi
509
510
if let result = block.call(compiled, arguments.to_array()) then
511
block.return_value(result)
512
else
513
block.return_value(LLVM.Values.integer(LLVM.Types.i32, bigint.zero))
514
fi
515
516
module.add_function(wrapper)
517
si
518
519
// Builds a `string[]` of the command-line arguments, starting in
520
// `block` and leaving the wrapper's last block to carry on in.
521
_command_line(wrapper: FUNCTION, block: LLVM.BLOCK, strings: LLVM_STRINGS, arrays: LLVM_ARRAYS, type: CLASS_INSTANCE) -> LLVM.Value is
522
let i32 = LLVM.Types.i32
523
524
let count = block.call(strings.runtime(LLVM_STRINGS.host_name("argument_count"), i32, []), [])!
525
let result = arrays.allocate(block, type, count)
526
let index = block.alloca(i32, 4)
527
528
block.store(LLVM.Values.i32(0), index, 4)
529
530
let test = wrapper.add_block("test")
531
let body = wrapper.add_block("body")
532
let done = wrapper.add_block("done")
533
534
block.branch(test)
535
536
let at = test.load(i32, index, 4)
537
538
test.branch(test.compare(LLVM.IntegerPredicate.SLT, at, count), body, done)
539
540
let current = body.load(i32, index, 4)
541
let argument = body.call(strings.runtime(LLVM_STRINGS.host_name("argument"), LLVM.Types.pointer, [i32]), [current])!
542
543
arrays.store(body, type, result, current, argument)
544
545
body.store(body.binary(LLVM.BinaryOperator.ADD, LLVM.IntegerFlags.NONE, current, LLVM.Values.i32(1)), index, 4)
546
body.branch(test)
547
548
return result
549
si
550
551
// The LLVM type a value of `type` is held in, a struct and an
552
// optional value type included once the classes are known.
553
_held(type: Semantic.Types.Type?) -> LLVM.Type? =>
554
if let objects = _objects then objects.held_type(type) else LLVM_TYPES.value_type(type) fi
555
556
// The LLVM function an instance is compiled into, with no body yet,
557
// or null, reported, where its signature has a type the target holds
558
// no values of.
559
_declare(instance: FUNCTION_INSTANCE, name: string) -> FUNCTION? is
560
let definition = instance.definition
561
562
let parameters = LIST[PARAMETER]()
563
564
// A struct method's receiver is the address of the struct, so
565
// the method changes it in place, as on .NET.
566
if definition.is_emitted_with_receiver then
567
parameters.add(PARAMETER(LLVM.Types.pointer, "self"))
568
fi
569
570
for (i, argument) in definition.arguments |> Ghul.Pipes.index() do
571
if let type = _held(instance.specialize(argument)) then
572
parameters.add(PARAMETER(type, "a{i}"))
573
else
574
_report(definition.location, "an argument of type {argument}")
575
return null
576
fi
577
od
578
579
let return_type = instance.specialize(definition.return_type)
580
let result = if LLVM_TYPES.is_void(return_type) then LLVM.Type.VOID else _held(return_type) fi
581
582
if !result? then
583
_report(definition.location, "a result of type {definition.return_type}")
584
return null
585
fi
586
587
return FUNCTION(name, result, parameters.to_array())
588
si
589
590
_lower(module: MODULE, strings: LLVM_STRINGS, arrays: LLVM_ARRAYS, objects: LLVM_OBJECTS, instance: FUNCTION_INSTANCE, function: FUNCTION, callee: (FUNCTION_INSTANCE) -> FUNCTION?) is
591
let definition = instance.definition
592
593
let lowering = LLVM_LOWERING(module, function, instance, instance.specialize(definition.return_type), callee, strings, arrays, objects)
594
595
if let debug = _debug_info then
596
lowering.debug_info = debug
597
// A function the compiler made from source the program
598
// wrote, as the entry made from a file's top-level
599
// statements is, has an internal name; it is placed at the
600
// source it was made from, so its statements keep their
601
// lines.
602
let location = if definition.location.is_internal /\ !definition.span.is_internal then definition.span else definition.location fi
603
604
lowering.debug_scope = debug.subprogram(function, instance.to_string(), location)
605
fi
606
607
lowering.lower(_bodies[definition])
608
609
for construct in lowering.unsupported do
610
_report(definition.location, construct)
611
od
612
si
613
614
si
615
616
// Finds a program's reach by lowering each body it reaches into a
617
// module that is thrown away.
618
class LLVM_DISCOVERY(
619
objects: LLVM_OBJECTS private,
620
reach: (FUNCTION_INSTANCE) -> void private,
621
report: (Source.LOCATION, string) -> void private
622
): DiscoveryTarget is
623
reach(instance: FUNCTION_INSTANCE) => _reach(instance)
624
625
is_instantiated(type: CLASS_INSTANCE) -> bool => _objects.is_instantiated(type)
626
627
note_instantiated(type: CLASS_INSTANCE) => _objects.note_instantiated(type)
628
629
report(location: Source.LOCATION, construct: string) => _report(location, construct)
630
si
631
si