Skip to content
← Back

src/ir/llvm/llvm_counted_loops.ghul

1
namespace IR.LLVMTarget is
2
use IR.Program
3
4
use Collections.MAP
5
6
use Semantic.Types.Type
7
8
use LLVM.BinaryOperator
9
use LLVM.IntegerFlags
10
use LLVM.IntegerPredicate
11
use LLVM.Types
12
13
use Values.Value
14
15
// How a counted `for` loop knows what it walks: an array, a collection
16
// of a known class, or a collection a run-time test of the receiver's
17
// class confirms, falling back to the iterator otherwise.
18
enum CountedRoute is
19
ARRAY,
20
EXACT,
21
GUARDED
22
si
23
24
// The collection a counted loop walks the storage of.
25
enum StorageKind is
26
ARRAY,
27
LIST,
28
MAP,
29
SET
30
si
31
32
// How a counted loop steps: through every element of an array up to a
33
// count, or through the entries of a hash table, skipping removed ones,
34
// reading each entry's key and value or its key alone.
35
enum CountedShape is
36
PLAIN,
37
PAIRS,
38
KEYS
39
si
40
41
// A `for` loop lowered over the storage it iterates: the array the
42
// elements are in, how many there are, and where the loop is. Where
43
// the receiver's class is only tested at run time, `flag` is the slot
44
// saying whether the test passed, and the iterator is used otherwise.
45
class COUNTED_LOOP is
46
iteration: FOR_ITERATION
47
is_active: bool public
48
flag: LLVM.Value? public
49
storage: LLVM.Value? public
50
count: LLVM.Value? public
51
index: LLVM.Value? public
52
array: CLASS_INSTANCE? public
53
shape: CountedShape public
54
hashes: LLVM.Value? public
55
values: LLVM.Value? public
56
value_array: CLASS_INSTANCE? public
57
58
/// Whether the copy of the loop being lowered is the one entered
59
/// only when the run-time test passed, which needs no test of its
60
/// own on each step.
61
is_counted_copy: bool public
62
63
init(iteration: FOR_ITERATION) is
64
self.iteration = iteration
65
si
66
si
67
68
partial LLVM_LOWERING is
69
// Records, when the local declared holds a `for` loop's iterator,
70
// the calls the loop makes on it, so they can be lowered over the
71
// iterated value's storage.
72
_note_iteration(local: LOCAL) is
73
if let iteration = local.iteration, objects = _objects, move_next = iteration.move_next, current = iteration.current /\ objects.is_built then
74
let loop = COUNTED_LOOP(iteration)
75
76
_counted_loops[iteration.get_iterator] = loop
77
_counted_loops[move_next] = loop
78
_counted_loops[current] = loop
79
fi
80
si
81
82
// Lowers `value` where it is one of a counted loop's calls,
83
// answering whether it did.
84
_lower_counted(value: Value) -> bool is
85
let loop: COUNTED_LOOP mut
86
87
if !_counted_loops.try_get_value(value, loop ref) then
88
return false
89
elif value == loop.iteration.get_iterator then
90
return _start_counted(loop, value)
91
elif !loop.is_active then
92
return false
93
elif value == loop.iteration.move_next then
94
_counted_step(loop, value, true)
95
else
96
_counted_step(loop, value, false)
97
fi
98
99
return true
100
si
101
102
_start_counted(loop: COUNTED_LOOP, value: Value) -> bool is
103
let objects = _objects!
104
let arrays = _arrays!
105
let lookup = IoC.CONTAINER.instance.innate_symbol_lookup
106
107
let call = cast Values.Call.INSTANCE?(value)
108
109
if !call? \/ call.from != loop.iteration.receiver \/ call.from.is_value_type then
110
return false
111
fi
112
113
let element = _specialize(loop.iteration.current!.type)
114
let receiver_type = _specialize(loop.iteration.receiver.type)
115
116
let moved = _held(loop.iteration.move_next!.type)
117
118
if !element? \/ !receiver_type? \/ !moved? \/ !(moved! =~ Types.i1) then
119
return false
120
fi
121
122
let candidates = Collections.LIST[(type: CLASS_INSTANCE, kind: StorageKind)]()
123
let has_other mut = false
124
125
if let array = arrays.array_of(receiver_type) then
126
candidates.add((array, StorageKind.ARRAY))
127
elif let static_class = objects.class_of(receiver_type) then
128
if let kind = _storage_kind(static_class) /\ objects.has_no_subclasses(static_class) then
129
candidates.add((static_class, kind))
130
else
131
return false
132
fi
133
elif let trait_type = objects.trait_of(receiver_type), implementors = objects.implementors(trait_type) then
134
for implementor in implementors do
135
if objects.is_allocated(implementor) then
136
if let kind = _storage_kind(implementor) then
137
candidates.add((implementor, kind))
138
else
139
has_other = true
140
fi
141
fi
142
od
143
else
144
return false
145
fi
146
147
if candidates.count == 0 then
148
return false
149
fi
150
151
let receiver = _value_of(call.from)
152
153
if !receiver? then
154
return true
155
fi
156
157
let family = Collections.LIST[(type: CLASS_INSTANCE, kind: StorageKind)]()
158
let route: CountedRoute mut
159
160
if let exact = _exact_class(receiver!), kind = _storage_kind(exact) /\ _contains(candidates, exact) then
161
family.add((exact, kind))
162
route = CountedRoute.EXACT
163
elif !has_other /\ candidates.count <= COUNTED_FAMILY_LIMIT /\ _one_shape(candidates) then
164
family.add_range(candidates)
165
route = if candidates.count == 1 /\ !objects.trait_of(receiver_type)? then CountedRoute.EXACT else CountedRoute.GUARDED fi
166
else
167
_preevaluated[call.from] = receiver!
168
value.accept(self)
169
170
return true
171
fi
172
173
if !_prepare_shape(loop, family[0], element) then
174
_preevaluated[call.from] = receiver!
175
value.accept(self)
176
177
return true
178
fi
179
180
let storage = _slot(Types.pointer)
181
let count = _slot(Types.i32)
182
let index = _slot(Types.i32)
183
184
loop.storage = storage
185
loop.count = count
186
loop.index = index
187
loop.hashes = _slot(Types.pointer)
188
loop.values = _slot(Types.pointer)
189
loop.is_active = true
190
191
_current.store(_i32(-1), index, 0)
192
193
if route == CountedRoute.EXACT then
194
_check_dereference(receiver!)
195
_load_storage(loop, family[0], receiver!)
196
_push(LLVM.Values.null_pointer)
197
else
198
let flag = _slot(Types.i1)
199
let iterator = _slot(Types.pointer)
200
201
loop.flag = flag
202
203
let check = _new_block()
204
let other = _new_block()
205
let join = _new_block()
206
207
_current.branch(_current.compare(IntegerPredicate.NE, receiver!, LLVM.Values.null_pointer), check, other)
208
209
_start(check)
210
let descriptor = _strings!.load_descriptor(_current, receiver!)
211
212
for member in family do
213
let matched = _new_block()
214
let next = _new_block()
215
216
_current.branch(_current.compare(IntegerPredicate.EQ, descriptor, LLVM.Values.global(objects.descriptor_name(member.type))), matched, next)
217
218
_start(matched)
219
_current.store(LLVM.Values.boolean(true), flag, 0)
220
_load_storage(loop, member, receiver!)
221
_current.branch(join)
222
223
_start(next)
224
od
225
226
_current.branch(other)
227
228
_start(other)
229
_preevaluated[call.from] = receiver!
230
value.accept(self)
231
232
if let made = _pop() then
233
_current.store(made, iterator, 0)
234
fi
235
236
_current.branch(join)
237
238
_start(join)
239
_push(_current.load(Types.pointer, iterator, 0))
240
fi
241
242
return true
243
si
244
245
// The collection `type` is, where a counted loop can walk its
246
// storage.
247
_storage_kind(type: CLASS_INSTANCE) -> StorageKind? is
248
let objects = _objects!
249
let lookup = IoC.CONTAINER.instance.innate_symbol_lookup
250
251
if objects.is_array(type) then
252
return StorageKind.ARRAY
253
elif let list = lookup.get_list_class() /\ type.definition == list then
254
return StorageKind.LIST
255
elif let map = lookup.get_map_class() /\ type.definition == map then
256
return StorageKind.MAP
257
elif let set = lookup.get_set_class() /\ type.definition == set then
258
return StorageKind.SET
259
fi
260
261
return null
262
si
263
264
_shape_of(kind: StorageKind) -> CountedShape =>
265
if kind == StorageKind.MAP then CountedShape.PAIRS elif kind == StorageKind.SET then CountedShape.KEYS else CountedShape.PLAIN fi
266
267
_one_shape(family: Collections.List[(type: CLASS_INSTANCE, kind: StorageKind)]) -> bool is
268
for member in family do
269
if _shape_of(member.kind) != _shape_of(family[0].kind) then
270
return false
271
fi
272
od
273
274
return true
275
si
276
277
_contains(family: Collections.List[(type: CLASS_INSTANCE, kind: StorageKind)], type: CLASS_INSTANCE) -> bool is
278
for member in family do
279
if member.type =~ type then
280
return true
281
fi
282
od
283
284
return false
285
si
286
287
// Settles how `loop` steps and reads its elements, from `member`, the
288
// first class it walks, and `element`, the type of what it reads.
289
// False where the arrays it reads cannot be found.
290
_prepare_shape(loop: COUNTED_LOOP, member: (type: CLASS_INSTANCE, kind: StorageKind), element: Type) -> bool is
291
let arrays = _arrays!
292
let lookup = IoC.CONTAINER.instance.innate_symbol_lookup
293
294
loop.shape = _shape_of(member.kind)
295
296
if loop.shape == CountedShape.PLAIN then
297
loop.array = arrays.array_of(lookup.get_array_type(element)) ?? arrays.array_of(lookup.get_array_type(lookup.get_object_type()))
298
return loop.array?
299
fi
300
301
let map = if member.kind == StorageKind.SET then _field_class(member.type, "_map") else member.type fi
302
303
if !map? then
304
return false
305
fi
306
307
loop.array = _field_array(map!, "_keys")
308
loop.value_array = _field_array(map!, "_values")
309
310
return loop.array? /\ (loop.shape == CountedShape.KEYS \/ loop.value_array?)
311
si
312
313
_field(type: CLASS_INSTANCE, name: string) -> (position: int, type: Type)? is
314
for (`field, field_type, position) in _objects!.fields_of(type) do
315
if `field.name =~ name \/ `field.name =~ "${name}" then
316
return (position, field_type)
317
fi
318
od
319
320
return null
321
si
322
323
_field_class(type: CLASS_INSTANCE, name: string) -> CLASS_INSTANCE? =>
324
if let f = _field(type, name) then _objects!.class_of(f.type) else null fi
325
326
_field_array(type: CLASS_INSTANCE, name: string) -> CLASS_INSTANCE? =>
327
if let f = _field(type, name) then _arrays!.array_of(f.type) else null fi
328
329
_load_field(type: CLASS_INSTANCE, object: LLVM.Value, name: string, as: LLVM.Type) -> LLVM.Value? =>
330
if let f = _field(type, name) then
331
_current.load(as, _current.element_pointer(_objects!.struct_type(type), object, [_i32(0), _i32(f.position)], true), 0)
332
else
333
null
334
fi
335
336
// Stores the storage of `receiver`, a `member`, where `loop` reads
337
// it, as the collection's own iterator takes it when it is made.
338
_load_storage(loop: COUNTED_LOOP, member: (type: CLASS_INSTANCE, kind: StorageKind), receiver: LLVM.Value) is
339
let map_type: CLASS_INSTANCE mut
340
let map: LLVM.Value mut
341
342
if member.kind == StorageKind.ARRAY then
343
_current.store(receiver, loop.storage!, 0)
344
_current.store(_arrays!.count(_current, receiver), loop.count!, 0)
345
return
346
elif member.kind == StorageKind.LIST then
347
if let items = _load_field(member.type, receiver, "_items", Types.pointer), counted = _load_field(member.type, receiver, "_count", Types.i32) then
348
_current.store(items, loop.storage!, 0)
349
_current.store(counted, loop.count!, 0)
350
else
351
_report("a list's storage")
352
fi
353
354
return
355
elif member.kind == StorageKind.SET then
356
if let inner = _field_class(member.type, "_map"), loaded = _load_field(member.type, receiver, "_map", Types.pointer) then
357
map_type = inner
358
map = loaded
359
else
360
_report("a set's storage")
361
return
362
fi
363
else
364
map_type = member.type
365
map = receiver
366
fi
367
368
if let hashes = _load_field(map_type, map, "_hashes", Types.pointer), keys = _load_field(map_type, map, "_keys", Types.pointer), values = _load_field(map_type, map, "_values", Types.pointer), used = _load_field(map_type, map, "_used", Types.i32) then
369
_current.store(hashes, loop.hashes!, 0)
370
_current.store(keys, loop.storage!, 0)
371
_current.store(values, loop.values!, 0)
372
_current.store(used, loop.count!, 0)
373
else
374
_report("a map's storage")
375
fi
376
si
377
378
// A loop whose body is lowered at most this many instructions large
379
// is lowered twice where its receiver is tested at run time: once
380
// walking the storage with no test per step, and once testing the
381
// flag on each step, which the iterator path needs.
382
COUNTED_COPY_LIMIT: int static => 80
383
384
// The guarded counted loop `loop` is the loop of, where it is one:
385
// its exit tests that loop's move to the next element.
386
_guarded_loop_of(loop: Values.LOOP) -> COUNTED_LOOP? is
387
if _counted_loops.count == 0 then
388
return null
389
fi
390
391
for value in loop.body.values do
392
if let exit: Values.BREAK = value then
393
for operand in exit.operands do
394
let counted: COUNTED_LOOP mut
395
396
if _counted_loops.try_get_value(operand, counted ref) /\ counted.is_active /\ counted.flag? /\ operand == counted.iteration.move_next then
397
return counted
398
fi
399
od
400
401
return null
402
fi
403
od
404
405
return null
406
si
407
408
// Lowers `loop` once testing the flag on each step, and again with
409
// no test where that copy is small, entering the second where the
410
// run-time test passed.
411
_lower_loop_twice(loop: Values.LOOP, counted: COUNTED_LOOP) is
412
let end = _new_block()
413
let depth = _stack.count
414
let dispatch = _new_block()
415
416
_branch(dispatch)
417
418
let first_block = _function.blocks.count
419
let dynamic_header = _lower_loop_copy(loop, end, depth)
420
421
let size mut = 0
422
423
for i in first_block.._function.blocks.count do
424
size = size + _function.blocks[i].instructions.count
425
od
426
427
if size <= COUNTED_COPY_LIMIT then
428
counted.is_counted_copy = true
429
430
let counted_header = _lower_loop_copy(loop, end, depth)
431
432
counted.is_counted_copy = false
433
434
dispatch.branch(dispatch.load(Types.i1, counted.flag!, 0), counted_header, dynamic_header)
435
else
436
dispatch.branch(dynamic_header)
437
fi
438
439
_start(end)
440
441
_check_depth(depth, "loop")
442
si
443
444
_lower_loop_copy(loop: Values.LOOP, end: LLVM.BLOCK, depth: int) -> LLVM.BLOCK is
445
let header = _new_block()
446
447
_labels.add((loop, false, end, null, depth))
448
_labels.add((loop, true, header, null, depth))
449
450
_start(header)
451
452
for value in loop.body.values do
453
gen(value)
454
od
455
456
if !_is_terminated then
457
_branch(header)
458
fi
459
460
_labels.remove_at(_labels.count - 1)
461
_labels.remove_at(_labels.count - 1)
462
463
return header
464
si
465
466
// A guarded loop tests the receiver against at most this many
467
// collection classes.
468
COUNTED_FAMILY_LIMIT: int static => 8
469
470
// A counted loop's move to the next element, or its read of the
471
// element it is at; through the iterator where the run-time test
472
// did not pass.
473
_counted_step(loop: COUNTED_LOOP, value: Value, is_move: bool) is
474
if let flag = loop.flag /\ !loop.is_counted_copy then
475
let held = _held(value.type)
476
477
if !held? then
478
_report("a counted loop's element")
479
return
480
fi
481
482
let result = _slot(held!)
483
let counted = _new_block()
484
let other = _new_block()
485
let join = _new_block()
486
487
_current.branch(_current.load(Types.i1, flag, 0), counted, other)
488
489
_start(counted)
490
let stepped = _counted_value(loop, value, is_move)
491
_current.store(stepped, result, 0)
492
_current.branch(join)
493
494
_start(other)
495
value.accept(self)
496
497
if let made = _pop() then
498
_current.store(made, result, 0)
499
fi
500
501
_current.branch(join)
502
503
_start(join)
504
_push(_current.load(held!, result, 0))
505
else
506
_push(_counted_value(loop, value, is_move))
507
fi
508
si
509
510
_counted_value(loop: COUNTED_LOOP, value: Value, is_move: bool) -> LLVM.Value is
511
let index = loop.index!
512
let arrays = _arrays!
513
514
if is_move then
515
let next = _current.binary(BinaryOperator.ADD, IntegerFlags.NONE, _current.load(Types.i32, index, 0), _i32(1))
516
517
_current.store(next, index, 0)
518
519
if loop.shape != CountedShape.PLAIN then
520
_skip_removed(loop)
521
fi
522
523
let at = _current.load(Types.i32, index, 0)
524
525
return _current.compare(IntegerPredicate.SLT, at, _current.load(Types.i32, loop.count!, 0))
526
fi
527
528
let at = _current.load(Types.i32, index, 0)
529
let key = arrays.load(_current, loop.array!, _current.load(Types.pointer, loop.storage!, 0), at)
530
531
if loop.shape != CountedShape.PAIRS then
532
return key
533
fi
534
535
let element = arrays.load(_current, loop.value_array!, _current.load(Types.pointer, loop.values!, 0), at)
536
537
return _pair(value.type, key, element)
538
si
539
540
// Moves `loop`'s index on past the removed entries of a hash table,
541
// whose hashes are negative, as the table's own iterator does.
542
_skip_removed(loop: COUNTED_LOOP) is
543
let arrays = _arrays!
544
let lookup = IoC.CONTAINER.instance.innate_symbol_lookup
545
let hashes_array = arrays.array_of(lookup.get_array_type(lookup.get_int_type()))!
546
547
let check = _new_block()
548
let test = _new_block()
549
let skip = _new_block()
550
let done = _new_block()
551
552
_current.branch(check)
553
554
_start(check)
555
let at = _current.load(Types.i32, loop.index!, 0)
556
_current.branch(_current.compare(IntegerPredicate.SLT, at, _current.load(Types.i32, loop.count!, 0)), test, done)
557
558
_start(test)
559
let hash = arrays.load(_current, hashes_array, _current.load(Types.pointer, loop.hashes!, 0), at)
560
_current.branch(_current.compare(IntegerPredicate.SLT, hash, _i32(0)), skip, done)
561
562
_start(skip)
563
_current.store(_current.binary(BinaryOperator.ADD, IntegerFlags.NONE, at, _i32(1)), loop.index!, 0)
564
_current.branch(check)
565
566
_start(done)
567
si
568
569
// A key and value pair of `type` holding `key` and `element`.
570
_pair(type: Type?, key: LLVM.Value, element: LLVM.Value) -> LLVM.Value is
571
let objects = _objects!
572
let pair = objects.class_of(_specialize(type))
573
let held = _held(type)
574
575
if !pair? \/ !held? then
576
_report("a map entry")
577
return key
578
fi
579
580
let key_field = pair.definition.find_direct("_key")
581
let value_field = pair.definition.find_direct("_value")
582
583
if let key_symbol = key_field, value_symbol = value_field, key_at = objects.field_position(key_symbol), value_at = objects.field_position(value_symbol) then
584
let with_key = _insert_member(LLVM_TYPES.zero(held!), key, key_at, pair.specialize(key_symbol.type))
585
586
return _insert_member(with_key, element, value_at, pair.specialize(value_symbol.type))
587
fi
588
589
_report("a map entry")
590
return key
591
si
592
si
593
si