Skip to content
← Back

src/ir/llvm/llvm_strings.ghul

1
namespace IR.LLVMTarget is
2
use Collections.LIST
3
use Collections.MAP
4
5
use LLVM.BLOCK
6
use LLVM.FUNCTION
7
use LLVM.GLOBAL_VARIABLE
8
use LLVM.Intrinsics
9
use LLVM.Linkage
10
use LLVM.MODULE
11
use LLVM.PARAMETER
12
use LLVM.Types
13
use LLVM.Values
14
15
/// A string on the LLVM target: one object holding the string type's
16
/// descriptor, a cached hash, the number of UTF-16 code units and the
17
/// code units themselves, laid out as `{ ptr, i32, i32, [N x i16] }`.
18
///
19
/// This builds what strings need beyond the lowering of each body: one
20
/// constant global per distinct literal, and the functions the native
21
/// runtime calls to make the program's strings.
22
class LLVM_STRINGS is
23
_module: MODULE
24
_literals: MAP[string, LLVM.Value]
25
_is_descriptor_used: bool
26
27
/// The offset of the cached hash within a string.
28
HASH_OFFSET: int static => 8
29
30
/// The offset of the count of code units within a string.
31
LENGTH_OFFSET: int static => 12
32
33
/// The offset of the first code unit within a string.
34
CHARS_OFFSET: int static => 16
35
36
/// The name of the global that stands for the string type's
37
/// descriptor.
38
DESCRIPTOR_NAME: string static => "string.$descriptor"
39
40
/// The name of the function the runtime calls to make a string.
41
MAKE_STRING_NAME: string static => "$ghul_make_string"
42
43
/// The name of the function the runtime calls to make a `ubyte[]`.
44
MAKE_BYTES_NAME: string static => "$ghul_make_bytes"
45
46
/// The name of the function the runtime calls to describe an
47
/// exception nothing caught.
48
REPORT_UNHANDLED_NAME: string static => "$ghul_report_unhandled"
49
50
/// The name of the function the runtime calls to make the exception
51
/// a read through null throws.
52
MAKE_NULL_REFERENCE_NAME: string static => "$ghul_make_null_reference"
53
54
/// The name of the runtime's function that throws what
55
/// `$ghul_make_null_reference` makes.
56
THROW_NULL_REFERENCE_NAME: string static => "$ghul_throw_null_reference"
57
58
/// The name of the runtime's host operation for `host.<operation>`.
59
host_name(operation: string) -> string static => "$ghul_host_{operation}"
60
61
_names: LLVM_NAMES
62
63
/// - module: where the literals and functions are added
64
init(module: MODULE) is
65
init(module, LLVM_NAMES())
66
si
67
68
/// - module: where the literals and functions are added
69
/// - names: the names the module's globals are given
70
init(module: MODULE, names: LLVM_NAMES) is
71
_module = module
72
_names = names
73
_literals = MAP[string, LLVM.Value]()
74
si
75
76
/// The hash `string.get_hash_code` answers for `text`, so a literal's
77
/// cached hash agrees with one computed at run time.
78
hash(text: string) -> int static is
79
let hash mut = -2128831035
80
81
for unit in text do
82
hash = (hash ^ cast int(unit)) * 16777619
83
od
84
85
return hash
86
si
87
88
/// The string type's descriptor, which the string class adds with
89
/// the other descriptors.
90
descriptor: LLVM.Value is
91
_is_descriptor_used = true
92
93
return Values.global(DESCRIPTOR_NAME)
94
si
95
96
/// Adds a placeholder for the string type's descriptor where strings
97
/// were made, for a program whose core library declares no string
98
/// type and so has no string class to describe them.
99
add_placeholder_descriptor() is
100
if !_is_descriptor_used then
101
return
102
fi
103
104
let global = GLOBAL_VARIABLE(DESCRIPTOR_NAME, Types.i8, Values.zero(Types.i8), true)
105
106
global.linkage = Linkage.INTERNAL
107
108
_module.add_global(global)
109
si
110
111
/// The label of the global holding the literal `text`: up to its
112
/// first 24 code units, each letter or digit kept and anything else
113
/// written as `_`.
114
///
115
/// - text: the literal's text
116
literal_label(text: string) -> string static is
117
let result = Text.STRING_BUILDER("$literal.")
118
let count = if text.length < 24 then text.length else 24 fi
119
120
for i in 0..count do
121
let unit = text[i]
122
123
if (unit >= 'a' /\ unit <= 'z') \/ (unit >= 'A' /\ unit <= 'Z') \/ (unit >= '0' /\ unit <= '9') then
124
result.append(unit)
125
else
126
result.append('_')
127
fi
128
od
129
130
return result.to_string()
131
si
132
133
/// The constant global holding the literal `text`. Every literal
134
/// with the same text is the same object, as on .NET.
135
literal(text: string) -> LLVM.Value is
136
let found: LLVM.Value mut
137
138
if _literals.try_get_value(text, found ref) then
139
return found
140
fi
141
142
let units = LIST[LLVM.Value]()
143
144
for unit in text do
145
units.add(Values.integer(Types.i16, bigint(cast int(unit))))
146
od
147
148
let chars = LLVM.Type.ARRAY(text.length, Types.i16)
149
let type = Types.structure([Types.pointer, Types.i32, Types.i32, chars])
150
151
let initializer =
152
LLVM.Value.AGGREGATE(
153
[
154
descriptor,
155
Values.i32(hash(text)),
156
Values.i32(text.length),
157
LLVM.Value.AGGREGATE(units.to_array(), chars)
158
],
159
type)
160
161
let global = GLOBAL_VARIABLE(_names.unique(literal_label(text)), type, initializer, true)
162
163
global.linkage = Linkage.PRIVATE
164
global.alignment = 8
165
166
_module.add_global(global)
167
168
let reference = global.reference
169
170
_literals[text] = reference
171
172
return reference
173
si
174
175
/// The address of the first code unit of the string `text` points at.
176
chars(block: BLOCK, text: LLVM.Value) -> LLVM.Value =>
177
block.element_pointer(Types.i8, text, [Values.i32(CHARS_OFFSET)], true)
178
179
/// The number of code units in the string `text` points at.
180
length(block: BLOCK, text: LLVM.Value) -> LLVM.Value =>
181
block.load(Types.i32, block.element_pointer(Types.i8, text, [Values.i32(LENGTH_OFFSET)], true), 4)
182
183
/// The code unit at `index` in the string `text` points at, as the
184
/// `i32` a `char` is held in. The index is not checked.
185
char_at(block: BLOCK, text: LLVM.Value, index: LLVM.Value) -> LLVM.Value is
186
let offset = block.binary(LLVM.BinaryOperator.SHL, LLVM.IntegerFlags.NONE, index, Values.i32(1))
187
let unit = block.load(Types.i16, block.element_pointer(Types.i8, chars(block, text), [offset], true), 2)
188
189
return block.convert(LLVM.Conversion.ZERO_EXTEND, unit, Types.i32)
190
si
191
192
/// A new string of `length` code units, as yet unwritten, from the
193
/// allocator for objects that hold no references. Only the header is
194
/// written, so every caller writes every code unit.
195
allocate(block: BLOCK, length: LLVM.Value) -> LLVM.Value is
196
let bytes = block.binary(LLVM.BinaryOperator.SHL, LLVM.IntegerFlags.NONE, block.convert(LLVM.Conversion.SIGN_EXTEND, length, Types.i64), Values.i64(1L))
197
let size = block.binary(LLVM.BinaryOperator.ADD, LLVM.IntegerFlags.NONE, bytes, Values.i64(cast long(CHARS_OFFSET)))
198
199
let result = _allocate_unzeroed(block, descriptor, size)
200
201
block.store(Values.i32(0), block.element_pointer(Types.i8, result, [Values.i32(HASH_OFFSET)], true), 4)
202
block.store(length, block.element_pointer(Types.i8, result, [Values.i32(LENGTH_OFFSET)], true), 4)
203
204
return result
205
si
206
207
// Copies `count` code units from `from` to `to`.
208
_copy(block: BLOCK, to: LLVM.Value, from: LLVM.Value, count: LLVM.Value) is
209
let bytes = block.binary(LLVM.BinaryOperator.SHL, LLVM.IntegerFlags.NONE, block.convert(LLVM.Conversion.SIGN_EXTEND, count, Types.i64), Values.i64(1L))
210
211
block.call(_module.declare_intrinsic(Intrinsics.memcpy()), [to, from, bytes, Values.boolean(false)])
212
si
213
214
// The address `count` code units on from `units`.
215
_advance(block: BLOCK, units: LLVM.Value, count: LLVM.Value) -> LLVM.Value =>
216
block.element_pointer(Types.i16, units, [count], true)
217
218
/// The function that joins two strings, either of which may be
219
/// null and is then taken as empty, into a new one.
220
concat_function: FUNCTION =>
221
_helper("string.$concat", Types.pointer, [Types.pointer, Types.pointer], function is
222
let block = function.add_block("entry")
223
let empty = literal("")
224
225
let left = block.select(block.compare(LLVM.IntegerPredicate.EQ, function.parameter(0), Values.null_pointer), empty, function.parameter(0))
226
let right = block.select(block.compare(LLVM.IntegerPredicate.EQ, function.parameter(1), Values.null_pointer), empty, function.parameter(1))
227
228
let left_length = length(block, left)
229
let right_length = length(block, right)
230
231
let result = allocate(block, block.binary(LLVM.BinaryOperator.ADD, LLVM.IntegerFlags.NONE, left_length, right_length))
232
let to = chars(block, result)
233
234
_copy(block, to, chars(block, left), left_length)
235
_copy(block, _advance(block, to, left_length), chars(block, right), right_length)
236
237
block.return_value(result)
238
si)
239
240
/// The function that answers whether two strings, either of which
241
/// may be null, hold the same code units: two nulls are equal, and
242
/// a null is equal to no string.
243
equals_function: FUNCTION =>
244
_helper("string.$equals", Types.i1, [Types.pointer, Types.pointer], function is
245
let left = function.parameter(0)
246
let right = function.parameter(1)
247
248
let entry = function.add_block("entry")
249
let same = function.add_block("same")
250
let present = function.add_block("present")
251
let lengths = function.add_block("lengths")
252
let compare = function.add_block("compare")
253
let different = function.add_block("different")
254
255
entry.branch(entry.compare(LLVM.IntegerPredicate.EQ, left, right), same, present)
256
257
same.return_value(Values.boolean(true))
258
259
let either_null =
260
present.binary(
261
LLVM.BinaryOperator.OR,
262
LLVM.IntegerFlags.NONE,
263
present.compare(LLVM.IntegerPredicate.EQ, left, Values.null_pointer),
264
present.compare(LLVM.IntegerPredicate.EQ, right, Values.null_pointer))
265
266
present.branch(either_null, different, lengths)
267
268
let left_length = lengths.load(Types.i32, lengths.element_pointer(Types.i8, left, [Values.i32(LENGTH_OFFSET)], true), 4)
269
let right_length = lengths.load(Types.i32, lengths.element_pointer(Types.i8, right, [Values.i32(LENGTH_OFFSET)], true), 4)
270
271
lengths.branch(lengths.compare(LLVM.IntegerPredicate.NE, left_length, right_length), different, compare)
272
273
different.return_value(Values.boolean(false))
274
275
let bytes = compare.binary(LLVM.BinaryOperator.SHL, LLVM.IntegerFlags.NONE, compare.convert(LLVM.Conversion.SIGN_EXTEND, left_length, Types.i64), Values.i64(1L))
276
let order = compare.call(runtime("memcmp", Types.i32, [Types.pointer, Types.pointer, Types.i64]), [chars(compare, left), chars(compare, right), bytes])!
277
278
compare.return_value(compare.compare(LLVM.IntegerPredicate.EQ, order, Values.i32(0)))
279
si)
280
281
/// The function that copies `count` code units of a string from
282
/// `start` into a new string. The range is not checked.
283
substring_function: FUNCTION =>
284
_helper("string.$substring", Types.pointer, [Types.pointer, Types.i32, Types.i32], function is
285
let block = function.add_block("entry")
286
let count = function.parameter(2)
287
288
let result = allocate(block, count)
289
290
_copy(block, chars(block, result), _advance(block, chars(block, function.parameter(0)), function.parameter(1)), count)
291
292
block.return_value(result)
293
si)
294
295
/// The function that makes a string of the one code unit it is
296
/// passed, held as an `i32`.
297
from_char_function: FUNCTION =>
298
_helper("string.$from_char", Types.pointer, [Types.i32], function is
299
let block = function.add_block("entry")
300
301
let result = allocate(block, Values.i32(1))
302
303
block.store(block.convert(LLVM.Conversion.TRUNCATE, function.parameter(0), Types.i16), chars(block, result), 2)
304
305
block.return_value(result)
306
si)
307
308
/// The function that copies `count` code units of a string from
309
/// `start` into an array of `char` from `at` on. An array of `char`
310
/// has a string's layout, so the copy is one block move. The ranges
311
/// are not checked.
312
copy_to_function: FUNCTION =>
313
_helper("string.$copy_to", LLVM.Type.VOID, [Types.pointer, Types.i32, Types.pointer, Types.i32, Types.i32], function is
314
let block = function.add_block("entry")
315
316
let from = _advance(block, chars(block, function.parameter(0)), function.parameter(1))
317
let to = _advance(block, chars(block, function.parameter(2)), function.parameter(3))
318
319
_copy(block, to, from, function.parameter(4))
320
321
block.return_void()
322
si)
323
324
// The function `name`, private to the module, built by `build` the
325
// first time it is asked for.
326
_helper(name: string, result: LLVM.Type, parameters: LLVM.Type[], build: FUNCTION -> void) -> FUNCTION is
327
if let existing = _module.function_named(name) then
328
return existing
329
fi
330
331
let declared = LIST[PARAMETER]()
332
333
for (i, type) in parameters |> Ghul.Pipes.index() do
334
declared.add(PARAMETER(type, "a{i}"))
335
od
336
337
let function = FUNCTION(name, result, declared.to_array())
338
339
function.linkage = Linkage.INTERNAL
340
341
build(function)
342
343
return _module.add_function(function)
344
si
345
346
/// Adds the function the native runtime calls to make a string, which
347
/// every program defines.
348
add_exports() is
349
_add_make_string()
350
si
351
352
// Copies `length` code units into a new string, through the runtime's
353
// allocator for objects that hold no references. The hash is left
354
// zero, as `string.get_hash_code` does not read it.
355
_add_make_string() is
356
let function =
357
FUNCTION(
358
MAKE_STRING_NAME,
359
Types.pointer,
360
[PARAMETER(Types.pointer, "chars"), PARAMETER(Types.i32, "length")])
361
362
let block = function.add_block("entry")
363
364
let length = function.parameter(1)
365
let result = allocate(block, length)
366
367
_copy(block, chars(block, result), function.parameter(0), length)
368
369
block.return_value(result)
370
371
_module.add_function(function)
372
si
373
374
/// The runtime's `$ghul_throw_null_reference`, declared the first time
375
/// it is asked for, as a cold function that does not return.
376
throw_null_reference: FUNCTION is
377
if let existing = _module.function_named(THROW_NULL_REFERENCE_NAME) then
378
return existing
379
fi
380
381
let function = runtime(THROW_NULL_REFERENCE_NAME, LLVM.Type.VOID, [])
382
383
function.attributes.add(LLVM.Attribute.FLAG("cold"))
384
function.attributes.add(LLVM.Attribute.FLAG("noreturn"))
385
386
return function
387
si
388
389
/// The module's declaration of `name`, a function the runtime
390
/// defines, adding it the first time it is asked for.
391
/// - name: the function's name
392
/// - result: the type it returns
393
/// - parameters: the types it takes
394
runtime(name: string, result: LLVM.Type, parameters: LLVM.Type[]) -> FUNCTION is
395
if let existing = _module.function_named(name) then
396
return existing
397
fi
398
399
let declared = LIST[PARAMETER]()
400
401
for (i, type) in parameters |> Ghul.Pipes.index() do
402
declared.add(PARAMETER(type, "a{i}"))
403
od
404
405
let function = FUNCTION(name, result, declared.to_array())
406
407
_describe_runtime(function)
408
409
return _module.add_function(function)
410
si
411
412
/// A new object of `size` bytes, its descriptor stored in its first
413
/// word and every other byte zero. The stores are the program's, so
414
/// the optimiser sees the object initialised and can drop a store
415
/// that is overwritten before anything reads it.
416
///
417
/// - block: where the allocation goes
418
/// - descriptor: the object's descriptor
419
/// - size: the object's size in bytes, an `i64`, header included
420
/// - scanned: whether the object can hold a pointer the collector
421
/// must follow
422
allocate_object(block: BLOCK, descriptor: LLVM.Value, size: LLVM.Value, scanned: bool) -> LLVM.Value is
423
let allocator = runtime(if scanned then "$ghul_alloc" else "$ghul_alloc_atomic" fi, Types.pointer, [Types.i64])
424
let result = block.call(allocator, [size])!
425
426
if !scanned \/ !SCANNED_MEMORY_IS_ZEROED then
427
block.call(_module.declare_intrinsic(Intrinsics.memset()), [result, Values.integer(Types.i8, 0n), size, Values.boolean(false)])
428
fi
429
430
block.store(descriptor, result, 8)
431
block.last_instruction.attach("invariant.group", _module.empty_metadata())
432
433
return result
434
si
435
436
// A new object of `size` bytes holding no references, with only its
437
// descriptor written.
438
_allocate_unzeroed(block: BLOCK, descriptor: LLVM.Value, size: LLVM.Value) -> LLVM.Value is
439
let result = block.call(runtime("$ghul_alloc_atomic", Types.pointer, [Types.i64]), [size])!
440
441
block.store(descriptor, result, 8)
442
block.last_instruction.attach("invariant.group", _module.empty_metadata())
443
444
return result
445
si
446
447
/// The descriptor of the object `object` points at. An object's
448
/// descriptor is stored once, when it is allocated, and never changes,
449
/// which the load says, so the optimiser can carry a descriptor it
450
/// has seen stored, or loaded, across a call to code it cannot see.
451
///
452
/// - block: where the load goes
453
/// - object: the object
454
load_descriptor(block: BLOCK, object: LLVM.Value) -> LLVM.Value is
455
let descriptor = block.load(Types.pointer, object, 8)
456
457
block.last_instruction.attach("invariant.group", _module.empty_metadata())
458
459
return descriptor
460
si
461
462
/// Whether `$ghul_alloc` is described to the optimiser as answering
463
/// zeroed memory, as the collector does, so the program does not
464
/// zero what it allocates there.
465
SCANNED_MEMORY_IS_ZEROED: bool static => false
466
467
// Says what the optimiser cannot see for itself about a function the
468
// runtime defines, whose body is not in the module: that an
469
// allocation answers fresh memory of the size it was asked for,
470
// aligned to 16 bytes as the collector aligns everything, and
471
// which functions neither unwind nor touch memory they are not
472
// given.
473
_describe_runtime(function: FUNCTION) is
474
let name = function.name
475
476
if name =~ "$ghul_alloc" \/ name =~ "$ghul_alloc_atomic" then
477
let zeroed = name =~ "$ghul_alloc" /\ SCANNED_MEMORY_IS_ZEROED
478
479
function.result_attributes.add(LLVM.Attribute.FLAG("noalias"))
480
function.result_attributes.add(LLVM.Attribute.FLAG("nonnull"))
481
function.result_attributes.add(LLVM.Attribute.FLAG("align 16"))
482
function.attributes.add(LLVM.Attribute.FLAG("nounwind"))
483
function.attributes.add(LLVM.Attribute.INTEGER("allocsize", 0L))
484
function.attributes.add(LLVM.Attribute.FLAG(if zeroed then "allockind(\"alloc,zeroed\")" else "allockind(\"alloc,uninitialized\")" fi))
485
function.attributes.add(LLVM.Attribute.STRING("alloc-family", "ghul_gc"))
486
elif name =~ "$ghul_clone" then
487
function.result_attributes.add(LLVM.Attribute.FLAG("noalias"))
488
function.result_attributes.add(LLVM.Attribute.FLAG("nonnull"))
489
function.result_attributes.add(LLVM.Attribute.FLAG("align 16"))
490
function.attributes.add(LLVM.Attribute.FLAG("nounwind"))
491
elif name =~ "$ghul_identity_hash" then
492
function.attributes.add(LLVM.Attribute.FLAG("nounwind"))
493
function.attributes.add(LLVM.Attribute.FLAG("willreturn"))
494
function.attributes.add(LLVM.Attribute.FLAG("memory(none)"))
495
elif name =~ "memcmp" then
496
function.attributes.add(LLVM.Attribute.FLAG("nounwind"))
497
function.attributes.add(LLVM.Attribute.FLAG("willreturn"))
498
function.attributes.add(LLVM.Attribute.FLAG("memory(argmem: read)"))
499
elif name =~ "$ghul_throw" then
500
function.attributes.add(LLVM.Attribute.FLAG("cold"))
501
function.attributes.add(LLVM.Attribute.FLAG("noreturn"))
502
elif name =~ "$ghul_caught" then
503
function.attributes.add(LLVM.Attribute.FLAG("nounwind"))
504
function.attributes.add(LLVM.Attribute.FLAG("willreturn"))
505
fi
506
si
507
si
508
si