lib/std/arch/rv64/tests/bounds.rad 57.3 KiB raw
1
//! Recoverable backend capacity and symbol checks.
2
3
use std::arch::rv64;
4
use std::collections::dict;
5
use std::lang::alloc;
6
use std::lang::gen::bitset;
7
use std::lang::gen::data;
8
use std::lang::gen::labels;
9
use std::lang::gen::regalloc;
10
use std::lang::il;
11
use std::mem::heap;
12
use std::testing;
13
use rv64::emit;
14
use rv64::encode;
15
16
/// Reusable emitter allocation storage.
17
static MEMORY: [u8; 16777216] = [0; 16777216];
18
19
/// Create block and function label tables in `arena`.
20
fn tables(arena: &heap::Heap) -> labels::Labels throws (alloc::AllocError) {
21
    let mut blockOffsets: *mut [i32] = &mut [];
22
    try blockOffsets.resize(labels::MAX_BLOCKS_PER_FN, 0, arena);
23
    let mut funcEntries: *mut [dict::Entry] = &mut [];
24
    try funcEntries.resize(labels::FUNC_TABLE_SIZE, dict::Entry { key: &[], value: 0 }, arena);
25
    return labels::init(blockOffsets, funcEntries);
26
}
27
28
/// Create an empty dictionary of `size` entries in `arena`.
29
fn table(arena: &heap::Heap, size: u32) -> dict::Dict throws (alloc::AllocError) {
30
    let mut entries: *mut [dict::Entry] = &mut [];
31
    try entries.resize(size, dict::Entry { key: &[], value: 0 }, arena);
32
    return dict::init(entries);
33
}
34
35
/// An emitter whose arena is full reports the allocation failure and keeps its earlier output.
36
@test unsafe fn emissionCapacity() throws (testing::TestError) {
37
    let arena = heap::over(&mut MEMORY[..]);
38
    let labelTables = try! tables(arena);
39
    let mut e = try! emit::emitter(arena, false, labelTables);
40
    let reserved = e.pendingCalls.cap;
41
    for _ in 0 .. reserved {
42
        try! emit::recordCall(&mut e, "p::call");
43
    }
44
    // Take the rest of the arena after the reserved calls own their names.
45
    let mut rest: *mut [u8] = &mut [];
46
    try! rest.resize(heap::remaining(e.arena), 0, e.arena);
47
    let mut failed = false;
48
    try emit::recordCall(&mut e, "p::call") catch err {
49
        try testing::expect(err == rv64::Error::Allocation);
50
        set failed = true;
51
    };
52
    try testing::expect(failed);
53
    try testing::expect(e.pendingCalls.len == reserved);
54
}
55
56
/// A full function table rejects a new function without changing earlier entries.
57
@test unsafe fn functionTableCapacity() throws (testing::TestError) {
58
    let arena = heap::over(&mut MEMORY[..]);
59
    let mut funcEntries: *mut [dict::Entry] = &mut [];
60
    try! funcEntries.resize(2, dict::Entry { key: &[], value: 0 }, arena);
61
    let mut e = try! emit::emitter(arena, false, labels::init(&mut [], funcEntries));
62
    try! emit::recordFuncOffset(&mut e, "p::first");
63
    let mut failed = false;
64
    try emit::recordFuncOffset(&mut e, "p::second") catch err {
65
        let case rv64::Error::Capacity(limit) = err else {
66
            throw testing::TestError::Failed;
67
        };
68
        try testing::expect(limit == rv64::Limit::FunctionTable);
69
        set failed = true;
70
    };
71
    try testing::expect(failed);
72
    try testing::expect(dict::get(&e.labels.funcs, "p::first") == 0);
73
}
74
75
/// Data output and symbol maps reject insufficient, ambiguous, or oversized storage.
76
@test unsafe fn dataStorage() throws (testing::TestError) {
77
    let arena = heap::over(&mut MEMORY[..]);
78
    let labelTables = try! tables(arena);
79
    let syms = &[data::DataSym { name: "p::data", addr: 0x80002000 }];
80
    let two = &[
81
        data::DataSym { name: "p::data", addr: 0x80002000 },
82
        data::DataSym {
83
            name: "p::other", addr: 0x80002008
84
        },
85
    ];
86
    let map = try! data::buildMap(syms, try! table(arena, 4));
87
    let items = &[
88
        data::Data {
89
            name: "p::data",
90
            size: 8,
91
            alignment: 8,
92
            readOnly: false,
93
            isZeroInit: false,
94
            values: &[
95
                il::DataValue {
96
                    item: il::DataItem::Val { typ: il::Type::W64, val: 1 }, count: 1
97
                },
98
            ],
99
        },
100
    ];
101
    let mut bytes: [u8; 8] = [255; 8];
102
    let mut failed: u32 = 0;
103
    try data::emitSection(
104
        items, &map, &labelTables, 0x80000000, &mut bytes[.. 7], false
105
    ) catch err {
106
        try testing::expect(err == data::Error::Capacity);
107
        set failed += 1;
108
    };
109
    try data::buildMap(two, try! table(arena, 2)) catch err {
110
        try testing::expect(err == data::Error::Capacity);
111
        set failed += 1;
112
    };
113
    try data::buildMap(
114
        &[
115
            data::DataSym { name: "p::data", addr: 0x80002000 },
116
            data::DataSym {
117
                name: "p::data", addr: 0x80002008
118
            },
119
        ],
120
        try! table(arena, 4)
121
    ) catch err {
122
        try testing::expect(err == data::Error::Symbol);
123
        set failed += 1;
124
    };
125
    let repeated = &[
126
        data::Data {
127
            name: "p::data",
128
            size: 8,
129
            alignment: 8,
130
            readOnly: false,
131
            isZeroInit: false,
132
            values: &[
133
                il::DataValue {
134
                    item: il::DataItem::Val { typ: il::Type::W64, val: 1 }, count: 2
135
                },
136
            ],
137
        },
138
    ];
139
    try data::emitSection(
140
        repeated, &map, &labelTables, 0x80000000, &mut bytes[..], false
141
    ) catch err {
142
        try testing::expect(err == data::Error::Overflow);
143
        set failed += 1;
144
    };
145
    try testing::expect(failed == 4);
146
    let length = try data::emitSection(
147
        items, &map, &labelTables, 0x80000000, &mut bytes[..], false
148
    ) catch {
149
        throw testing::TestError::Failed;
150
    };
151
    try testing::expect(length == 8 and bytes[0] == 1);
152
}
153
154
/////////////////////////
155
// Hostile IL shapes   //
156
/////////////////////////
157
158
/// Storage for the IL of the hostile shape tests.
159
static SHAPE_STORAGE: [u8; 1048576] = [0; 1048576];
160
/// Scratch storage for the register allocation of the hostile shape tests.
161
static SHAPE_SCRATCH: [u8; 4194304] = [0; 4194304];
162
163
/// A register as a value.
164
fn val(n: u32) -> il::Val {
165
    return il::Val::Reg(il::Reg { n });
166
}
167
168
/// Append an instruction to a list that lives in `arena`.
169
fn push(list: &mut *mut [il::Instr], instr: il::Instr, arena: &heap::Heap) {
170
    try! list.append(instr, arena);
171
}
172
173
/// A block with the instructions, and no parameters.
174
fn blockOf(instrs: *[il::Instr]) -> il::Block {
175
    return il::Block {
176
        label: il::BlockLabel { base: "b", suffix: nil },
177
        params: &[],
178
        instrs,
179
        locs: &[],
180
        preds: &[],
181
        loopDepth: 0,
182
    };
183
}
184
185
/// Generate code for each function in order.
186
unsafe fn generateAll(funcs: *mut [il::Fn], layouts: &[il::Layout]) throws (rv64::Error) {
187
    try generateWith(funcs, layouts, labels::MAX_BLOCKS_PER_FN, labels::FUNC_TABLE_SIZE);
188
}
189
190
/// Generate code for each function in order, with label tables of the given sizes.
191
/// `funcTable` must be a power of two. Small tables keep the setup of a run short.
192
unsafe fn generateWith(
193
    funcs: *mut [il::Fn],
194
    layouts: &[il::Layout],
195
    maxBlocks: u32,
196
    funcTable: u32
197
) throws (rv64::Error) {
198
    let arena = heap::over(&mut MEMORY[..]);
199
    let mut blockOffsets: *mut [i32] = &mut [];
200
    try! blockOffsets.resize(maxBlocks, 0, arena);
201
    let mut funcEntries: *mut [dict::Entry] = &mut [];
202
    try! funcEntries.resize(funcTable, dict::Entry { key: &[], value: 0 }, arena);
203
    let labelTables = labels::fresh(blockOffsets, funcEntries);
204
    let scratch = heap::over(&mut SHAPE_SCRATCH[..]);
205
    let mut generator = try rv64::beginProgram(
206
        rv64::ProgramOptions {
207
            stack: rv64::StackCheck::Off,
208
            entryPatch: rv64::EntryPatch::None,
209
            debug: false,
210
            placement: rv64::image::Placement::Hosted,
211
        },
212
        arena,
213
        labelTables
214
    );
215
    for i in 0 .. funcs.len {
216
        try rv64::generateFunction(&mut generator, &funcs[i], layouts, scratch);
217
    }
218
}
219
220
/// A function without parameters and results.
221
fn voidFn(name: *[u8], blocks: *[il::Block], vals: *[il::Val]) -> il::Fn {
222
    return il::Fn {
223
        name,
224
        params: &[],
225
        returnType: il::ValType::Void,
226
        isExtern: false,
227
        isLeaf: false,
228
        blocks,
229
        vals,
230
        cases: &[],
231
        borrows: &[],
232
    };
233
}
234
235
/// A function that does nothing, which the other functions call.
236
fn target(arena: &heap::Heap) -> il::Fn {
237
    let mut instrs: *mut [il::Instr] = &mut [];
238
    push(&mut instrs, il::Instr::Ret { val: nil }, arena);
239
    let mut blocks: *mut [il::Block] = &mut [];
240
    try! blocks.append(blockOf(&instrs[..]), arena);
241
    return voidFn("target", &blocks[..], &[]);
242
}
243
244
/// Values that are live at once fill the registers, with a definition that nothing uses, and
245
/// more than the registers hold. Code generation spills instead of failing.
246
@test unsafe fn registerPressure() throws (testing::TestError) {
247
    for live in 14 .. 40 {
248
        let arena = heap::over(&mut SHAPE_STORAGE[..]);
249
        let mut instrs: *mut [il::Instr] = &mut [];
250
        for i in 0 .. live {
251
            push(
252
                &mut instrs,
253
                il::Instr::Copy {
254
                    dst: il::Reg { n: i }, val: il::Val::Imm(i as i64)
255
                },
256
                arena
257
            );
258
        }
259
        push(
260
            &mut instrs,
261
            il::Instr::BinOp {
262
                op: il::BinOp::Add,
263
                typ: il::Type::W64,
264
                dst: il::Reg { n: live },
265
                a: val(0),
266
                b: val(1),
267
            },
268
            arena
269
        );
270
        for i in 0 .. live {
271
            push(
272
                &mut instrs,
273
                il::Instr::BinOp {
274
                    op: il::BinOp::Add,
275
                    typ: il::Type::W64,
276
                    dst: il::Reg { n: live + 1 + i },
277
                    a: val(i),
278
                    b: val(live - 1 - i),
279
                },
280
                arena
281
            );
282
        }
283
        push(&mut instrs, il::Instr::Ret { val: nil }, arena);
284
        let mut blocks: *mut [il::Block] = &mut [];
285
        try! blocks.append(blockOf(&instrs[..]), arena);
286
        let mut funcs: *mut [il::Fn] = &mut [];
287
        try! funcs.append(voidFn("f", &blocks[..], &[]), arena);
288
        try generateAll(funcs, &[]) catch {
289
            throw testing::TestError::Failed;
290
        };
291
    }
292
}
293
294
/// Values that are live across a call need callee-saved registers, and there are fewer of
295
/// those than values. The rest are spilled.
296
@test unsafe fn registersAcrossCall() throws (testing::TestError) {
297
    for live in 6 .. 40 {
298
        let arena = heap::over(&mut SHAPE_STORAGE[..]);
299
        let mut instrs: *mut [il::Instr] = &mut [];
300
        for i in 0 .. live {
301
            push(
302
                &mut instrs,
303
                il::Instr::Copy {
304
                    dst: il::Reg { n: i }, val: il::Val::Imm(i as i64)
305
                },
306
                arena
307
            );
308
        }
309
        push(
310
            &mut instrs,
311
            il::Instr::Call {
312
                retTy: il::ValType::Void,
313
                dst: nil,
314
                func: il::Val::FnAddr("target"),
315
                args: il::ArgRange { start: 0, len: 0 },
316
            },
317
            arena
318
        );
319
        for i in 0 .. live {
320
            push(
321
                &mut instrs,
322
                il::Instr::BinOp {
323
                    op: il::BinOp::Add,
324
                    typ: il::Type::W64,
325
                    dst: il::Reg { n: live + i },
326
                    a: val(i),
327
                    b: val(live - 1 - i),
328
                },
329
                arena
330
            );
331
        }
332
        push(&mut instrs, il::Instr::Ret { val: nil }, arena);
333
        let mut blocks: *mut [il::Block] = &mut [];
334
        try! blocks.append(blockOf(&instrs[..]), arena);
335
        let mut funcs: *mut [il::Fn] = &mut [];
336
        try! funcs.append(target(arena), arena);
337
        try! funcs.append(voidFn("f", &blocks[..], &[]), arena);
338
        try generateAll(funcs, &[]) catch {
339
            throw testing::TestError::Failed;
340
        };
341
    }
342
}
343
344
/// A block with as many parameters as the backend allows, all live across a call.
345
@test unsafe fn manyBlockParameters() throws (testing::TestError) {
346
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
347
    let mut vals: *mut [il::Val] = &mut [];
348
    let mut params: *mut [il::Param] = &mut [];
349
    for i in 0 .. 16 {
350
        try! vals.append(il::Val::Imm(i as i64), arena);
351
        try! params.append(
352
            il::Param {
353
                value: il::Reg { n: i }, type: il::ValType::Data(il::Type::W64)
354
            },
355
            arena
356
        );
357
    }
358
    let mut entry: *mut [il::Instr] = &mut [];
359
    push(
360
        &mut entry,
361
        il::Instr::Jmp {
362
            target: 1, args: il::ArgRange { start: 0, len: 16 }
363
        },
364
        arena
365
    );
366
    let mut body: *mut [il::Instr] = &mut [];
367
    push(
368
        &mut body,
369
        il::Instr::Call {
370
            retTy: il::ValType::Void,
371
            dst: nil,
372
            func: il::Val::FnAddr("target"),
373
            args: il::ArgRange { start: 0, len: 0 },
374
        },
375
        arena
376
    );
377
    for i in 0 .. 16 {
378
        push(
379
            &mut body,
380
            il::Instr::BinOp {
381
                op: il::BinOp::Add,
382
                typ: il::Type::W64,
383
                dst: il::Reg { n: 16 + i },
384
                a: val(i),
385
                b: val(15 - i),
386
            },
387
            arena
388
        );
389
    }
390
    push(&mut body, il::Instr::Ret { val: nil }, arena);
391
    let mut blocks: *mut [il::Block] = &mut [];
392
    try! blocks.append(blockOf(&entry[..]), arena);
393
    try! blocks.append(
394
        il::Block {
395
            label: il::BlockLabel { base: "b", suffix: nil },
396
            params: &params[..],
397
            instrs: &body[..],
398
            locs: &[],
399
            preds: &[],
400
            loopDepth: 0,
401
        },
402
        arena
403
    );
404
    let mut funcs: *mut [il::Fn] = &mut [];
405
    try! funcs.append(target(arena), arena);
406
    try! funcs.append(voidFn("f", &blocks[..], &vals[..]), arena);
407
    try generateAll(funcs, &[]) catch {
408
        throw testing::TestError::Failed;
409
    };
410
}
411
412
/// Definition of register `dst` as the immediate `value`.
413
fn copyOf(dst: u32, value: i64) -> il::Instr {
414
    return il::Instr::Copy { dst: il::Reg { n: dst }, val: il::Val::Imm(value) };
415
}
416
417
/// Definition of register `dst` as the sum of registers `a` and `b`.
418
fn addOf(dst: u32, a: u32, b: u32) -> il::Instr {
419
    return il::Instr::BinOp {
420
        op: il::BinOp::Add, typ: il::Type::W64, dst: il::Reg { n: dst }, a: val(a), b: val(b)
421
    };
422
}
423
424
/// A call of `target` without arguments or result.
425
fn callTarget() -> il::Instr {
426
    return il::Instr::Call {
427
        retTy: il::ValType::Void,
428
        dst: nil,
429
        func: il::Val::FnAddr("target"),
430
        args: il::ArgRange { start: 0, len: 0 },
431
    };
432
}
433
434
/// Check that generating `funcs`, which end with the function "f", fails with the allocation
435
/// error instead of stopping the backend.
436
unsafe fn allocationFails(funcs: *mut [il::Fn]) throws (testing::TestError) {
437
    let mut failed = false;
438
    try generateAll(funcs, &[]) catch err {
439
        try testing::expect(err == rv64::Error::Allocation);
440
        set failed = true;
441
    };
442
    try testing::expect(failed);
443
}
444
445
/// A long-lived value takes a callee-saved register once the other registers are full, and
446
/// leaves too few of them for the values that are live across the later call. The backend
447
/// reports the failure, and does not stop.
448
@test unsafe fn calleeSavedExhausted() throws (testing::TestError) {
449
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
450
    let mut instrs: *mut [il::Instr] = &mut [];
451
    // Eleven values fill the temporary and argument registers, and a twelfth one spills over
452
    // to the first callee-saved register.
453
    for i in 0 .. 12 {
454
        push(&mut instrs, copyOf(i, i as i64), arena);
455
    }
456
    // Sum the eleven values, into results that nothing uses at the end.
457
    push(&mut instrs, addOf(12, 0, 1), arena);
458
    for i in 1 .. 10 {
459
        push(&mut instrs, addOf(12 + i, 11 + i, 1 + i), arena);
460
    }
461
    // Eleven values live across the call need all the callee-saved registers.
462
    for i in 0 .. 11 {
463
        push(&mut instrs, copyOf(22 + i, i as i64), arena);
464
    }
465
    push(&mut instrs, addOf(33, 11, 11), arena);
466
    push(&mut instrs, callTarget(), arena);
467
    push(&mut instrs, addOf(34, 22, 23), arena);
468
    for i in 1 .. 10 {
469
        push(&mut instrs, addOf(34 + i, 33 + i, 23 + i), arena);
470
    }
471
    push(&mut instrs, il::Instr::Ret { val: nil }, arena);
472
    let mut blocks: *mut [il::Block] = &mut [];
473
    try! blocks.append(blockOf(&instrs[..]), arena);
474
    let mut funcs: *mut [il::Fn] = &mut [];
475
    try! funcs.append(target(arena), arena);
476
    try! funcs.append(voidFn("f", &blocks[..], &[]), arena);
477
    try allocationFails(funcs);
478
}
479
480
/// Values that are live across different calls need callee-saved registers, but only the ones
481
/// that are live together compete for them. A value that lives through every call stays in a
482
/// register while the values of the single calls come and go.
483
@test unsafe fn calleeSavedAtOnePoint() throws (testing::TestError) {
484
    let config = rv64::targetConfig();
485
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
486
    // More calls than callee-saved registers. The block of a call defines the value `1 + k`,
487
    // which lives across the call, and adds it to the value `0`, which lives through all calls.
488
    let calls: u32 = 16;
489
    let mut blocks: *mut [il::Block] = &mut [];
490
    let mut entry: *mut [il::Instr] = &mut [];
491
    push(&mut entry, copyOf(0, 1), arena);
492
    push(&mut entry, jumpTo(1), arena);
493
    try! blocks.append(blockOf(&entry[..]), arena);
494
    for k in 0 .. calls {
495
        let mut instrs: *mut [il::Instr] = &mut [];
496
        push(&mut instrs, copyOf(1 + k, k as i64), arena);
497
        push(&mut instrs, callTarget(), arena);
498
        push(&mut instrs, addOf(1 + calls + k, 1 + k, 0), arena);
499
        push(&mut instrs, jumpTo(k + 2), arena);
500
        try! blocks.append(blockOf(&instrs[..]), arena);
501
    }
502
    let mut last: *mut [il::Instr] = &mut [];
503
    push(&mut last, il::Instr::Ret { val: val(0) }, arena);
504
    try! blocks.append(blockOf(&last[..]), arena);
505
    let mut funcs: *mut [il::Fn] = &mut [];
506
    try! funcs.append(
507
        il::Fn {
508
            name: "f",
509
            params: &[],
510
            returnType: il::ValType::Data(il::Type::W64),
511
            isExtern: false,
512
            isLeaf: false,
513
            blocks: &blocks[..],
514
            vals: &[],
515
            cases: &[],
516
            borrows: &[],
517
        },
518
        arena
519
    );
520
    let result = try regalloc::allocate(&funcs[0], &config, arena) catch {
521
        throw testing::TestError::Failed;
522
    };
523
    for n in 0 .. 1 + 2 * calls {
524
        try testing::expect(not regalloc::spill::isSpilled(&result.spill, il::Reg { n }));
525
    }
526
}
527
528
/// A block parameter that nothing uses still holds a register while the block is entered, so
529
/// the values that are live into the block leave room for it.
530
@test unsafe fn unusedBlockParameter() throws (testing::TestError) {
531
    for live in 20 .. 24 {
532
        let arena = heap::over(&mut SHAPE_STORAGE[..]);
533
        let mut vals: *mut [il::Val] = &mut [];
534
        try! vals.append(val(0), arena);
535
        let mut entry: *mut [il::Instr] = &mut [];
536
        for i in 0 .. live {
537
            push(&mut entry, copyOf(i, i as i64), arena);
538
        }
539
        push(
540
            &mut entry,
541
            il::Instr::Jmp {
542
                target: 1, args: il::ArgRange { start: 0, len: 1 }
543
            },
544
            arena
545
        );
546
        // The block sums all the values that flow in, and ignores its parameter.
547
        let mut body: *mut [il::Instr] = &mut [];
548
        push(&mut body, addOf(live + 1, 0, 1), arena);
549
        for i in 1 .. live - 1 {
550
            push(&mut body, addOf(live + 1 + i, live + i, 1 + i), arena);
551
        }
552
        push(&mut body, il::Instr::Ret { val: nil }, arena);
553
        let mut blocks: *mut [il::Block] = &mut [];
554
        try! blocks.append(blockOf(&entry[..]), arena);
555
        let mut unused: *mut [il::Param] = &mut [];
556
        try! unused.append(
557
            il::Param {
558
                value: il::Reg { n: live }, type: il::ValType::Data(il::Type::W64)
559
            },
560
            arena
561
        );
562
        try! blocks.append(
563
            il::Block {
564
                label: il::BlockLabel { base: "b", suffix: nil },
565
                params: &unused[..],
566
                instrs: &body[..],
567
                locs: &[],
568
                preds: &[],
569
                loopDepth: 0,
570
            },
571
            arena
572
        );
573
        let mut funcs: *mut [il::Fn] = &mut [];
574
        try! funcs.append(target(arena), arena);
575
        try! funcs.append(voidFn("f", &blocks[..], &vals[..]), arena);
576
        try generateAll(funcs, &[]) catch {
577
            throw testing::TestError::Failed;
578
        };
579
    }
580
}
581
582
/// Parameters beyond the argument registers are allocated like other values, and must not take
583
/// the register of a parameter that arrives in an argument register.
584
@test unsafe fn stackParameters() throws (testing::TestError) {
585
    let config = rv64::targetConfig();
586
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
587
    let mut params: *mut [il::Param] = &mut [];
588
    // The parameters beyond the eight registers have the lowest register numbers.
589
    for i in 0 .. 16 {
590
        try! params.append(
591
            il::Param {
592
                value: il::Reg { n: (i + 8) % 16 }, type: il::ValType::Data(il::Type::W64)
593
            },
594
            arena
595
        );
596
    }
597
    let mut instrs: *mut [il::Instr] = &mut [];
598
    push(&mut instrs, addOf(16, 0, 1), arena);
599
    for i in 1 .. 15 {
600
        push(&mut instrs, addOf(16 + i, 15 + i, 1 + i), arena);
601
    }
602
    push(&mut instrs, il::Instr::Ret { val: nil }, arena);
603
    let mut blocks: *mut [il::Block] = &mut [];
604
    try! blocks.append(blockOf(&instrs[..]), arena);
605
    let mut funcs: *mut [il::Fn] = &mut [];
606
    try! funcs.append(
607
        il::Fn {
608
            name: "f",
609
            params: &params[..],
610
            returnType: il::ValType::Void,
611
            isExtern: false,
612
            isLeaf: false,
613
            blocks: &blocks[..],
614
            vals: &[],
615
            cases: &[],
616
            borrows: &[],
617
        },
618
        arena
619
    );
620
    let result = try regalloc::allocate(&funcs[0], &config, arena) catch {
621
        throw testing::TestError::Failed;
622
    };
623
    // All sixteen values are live on entry, so no two of them share a register.
624
    for i in 0 .. 16 {
625
        let first = result.assignments[i] else {
626
            throw testing::TestError::Failed;
627
        };
628
        for j in i + 1 .. 16 {
629
            let second = result.assignments[j] else {
630
                throw testing::TestError::Failed;
631
            };
632
            try testing::expect(*first <> *second);
633
        }
634
    }
635
}
636
637
/// A conditional branch can pass arguments on both edges.
638
@test unsafe fn branchArgumentsOnBothEdges() throws (testing::TestError) {
639
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
640
    let mut vals: *mut [il::Val] = &mut [];
641
    try! vals.append(il::Val::Imm(1), arena);
642
    try! vals.append(il::Val::Imm(2), arena);
643
    let mut entry: *mut [il::Instr] = &mut [];
644
    push(
645
        &mut entry,
646
        il::Instr::Br {
647
            op: il::CmpOp::Eq,
648
            typ: il::Type::W64,
649
            a: val(0),
650
            b: il::Val::Imm(0),
651
            thenTarget: 1,
652
            thenArgs: il::ArgRange { start: 0, len: 1 },
653
            elseTarget: 2,
654
            elseArgs: il::ArgRange { start: 1, len: 1 },
655
        },
656
        arena
657
    );
658
    let mut first: *mut [il::Instr] = &mut [];
659
    push(&mut first, il::Instr::Ret { val: val(1) }, arena);
660
    let mut second: *mut [il::Instr] = &mut [];
661
    push(&mut second, il::Instr::Ret { val: val(2) }, arena);
662
    let mut blocks: *mut [il::Block] = &mut [];
663
    try! blocks.append(blockOf(&entry[..]), arena);
664
    try! blocks.append(
665
        il::Block {
666
            label: il::BlockLabel { base: "b", suffix: nil },
667
            params: &[
668
                il::Param { value: il::Reg { n: 1 }, type: il::ValType::Data(il::Type::W64) }
669
            ],
670
            instrs: &first[..],
671
            locs: &[],
672
            preds: &[],
673
            loopDepth: 0,
674
        },
675
        arena
676
    );
677
    try! blocks.append(
678
        il::Block {
679
            label: il::BlockLabel { base: "b", suffix: nil },
680
            params: &[
681
                il::Param { value: il::Reg { n: 2 }, type: il::ValType::Data(il::Type::W64) }
682
            ],
683
            instrs: &second[..],
684
            locs: &[],
685
            preds: &[],
686
            loopDepth: 0,
687
        },
688
        arena
689
    );
690
    let mut funcs: *mut [il::Fn] = &mut [];
691
    try! funcs.append(
692
        il::Fn {
693
            name: "f",
694
            params: &[
695
                il::Param { value: il::Reg { n: 0 }, type: il::ValType::Data(il::Type::W64) }
696
            ],
697
            returnType: il::ValType::Data(il::Type::W64),
698
            isExtern: false,
699
            isLeaf: true,
700
            blocks: &blocks[..],
701
            vals: &vals[..],
702
            cases: &[],
703
            borrows: &[],
704
        },
705
        arena
706
    );
707
    try generateAll(funcs, &[]) catch {
708
        throw testing::TestError::Failed;
709
    };
710
    // The code is the prologue-free function body: both moves exist, so it is longer than
711
    // a branch with arguments on one edge.
712
}
713
714
/// IL that violates a precondition of a pass is reported, and does not stop the backend.
715
@test unsafe fn malformedIl() throws (testing::TestError) {
716
    // A call to an address that is not a symbol or a register.
717
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
718
    let mut instrs: *mut [il::Instr] = &mut [];
719
    push(
720
        &mut instrs,
721
        il::Instr::Call {
722
            retTy: il::ValType::Void,
723
            dst: nil,
724
            func: il::Val::Imm(8),
725
            args: il::ArgRange { start: 0, len: 0 },
726
        },
727
        arena
728
    );
729
    push(&mut instrs, il::Instr::Ret { val: nil }, arena);
730
    let mut blocks: *mut [il::Block] = &mut [];
731
    try! blocks.append(blockOf(&instrs[..]), arena);
732
    let mut funcs: *mut [il::Fn] = &mut [];
733
    try! funcs.append(voidFn("f", &blocks[..], &[]), arena);
734
    let mut failed = false;
735
    try generateAll(funcs, &[]) catch err {
736
        try testing::expect(err == rv64::Error::Invalid);
737
        set failed = true;
738
    };
739
    try testing::expect(failed);
740
741
    // A jump with fewer arguments than the block has parameters.
742
    let arena2 = heap::over(&mut SHAPE_STORAGE[..]);
743
    let mut entry: *mut [il::Instr] = &mut [];
744
    push(
745
        &mut entry,
746
        il::Instr::Jmp { target: 1, args: il::ArgRange { start: 0, len: 0 } },
747
        arena2
748
    );
749
    let mut exit: *mut [il::Instr] = &mut [];
750
    push(&mut exit, il::Instr::Ret { val: nil }, arena2);
751
    let mut jumps: *mut [il::Block] = &mut [];
752
    try! jumps.append(blockOf(&entry[..]), arena2);
753
    try! jumps.append(
754
        il::Block {
755
            label: il::BlockLabel { base: "b", suffix: nil },
756
            params: &[
757
                il::Param { value: il::Reg { n: 0 }, type: il::ValType::Data(il::Type::W64) }
758
            ],
759
            instrs: &exit[..],
760
            locs: &[],
761
            preds: &[],
762
            loopDepth: 0,
763
        },
764
        arena2
765
    );
766
    let mut jumpFns: *mut [il::Fn] = &mut [];
767
    try! jumpFns.append(voidFn("f", &jumps[..], &[]), arena2);
768
    let mut counted = false;
769
    try generateAll(jumpFns, &[]) catch err {
770
        try testing::expect(err == rv64::Error::Invalid);
771
        set counted = true;
772
    };
773
    try testing::expect(counted);
774
775
    // A copy longer than a register can address.
776
    let arena3 = heap::over(&mut SHAPE_STORAGE[..]);
777
    let mut copies: *mut [il::Instr] = &mut [];
778
    push(&mut copies, il::Instr::Reserve { dst: il::Reg { n: 0 }, layout: 0 }, arena3);
779
    push(
780
        &mut copies,
781
        il::Instr::Blit {
782
            dst: il::Reg { n: 0 }, src: il::Reg { n: 0 }, layout: 1
783
        },
784
        arena3
785
    );
786
    push(&mut copies, il::Instr::Ret { val: nil }, arena3);
787
    let mut copyBlocks: *mut [il::Block] = &mut [];
788
    try! copyBlocks.append(blockOf(&copies[..]), arena3);
789
    let mut copyFns: *mut [il::Fn] = &mut [];
790
    try! copyFns.append(voidFn("f", &copyBlocks[..], &[]), arena3);
791
    let layouts = [
792
        il::Layout { size: 8,          alignment: 8, slots: &[], regions: 0 },
793
        il::Layout { size: 0x80000000, alignment: 8, slots: &[], regions: 0 },
794
    ];
795
    let mut wide = false;
796
    try generateAll(copyFns, &layouts[..]) catch err {
797
        try testing::expect(err == rv64::Error::Invalid);
798
        set wide = true;
799
    };
800
    try testing::expect(wide);
801
802
    // An object that needs more alignment than the stack has.
803
    let arena4 = heap::over(&mut SHAPE_STORAGE[..]);
804
    let mut aligned: *mut [il::Instr] = &mut [];
805
    push(&mut aligned, il::Instr::Reserve { dst: il::Reg { n: 0 }, layout: 0 }, arena4);
806
    push(&mut aligned, il::Instr::Ret { val: nil }, arena4);
807
    let mut alignedBlocks: *mut [il::Block] = &mut [];
808
    try! alignedBlocks.append(blockOf(&aligned[..]), arena4);
809
    let mut alignedFns: *mut [il::Fn] = &mut [];
810
    try! alignedFns.append(voidFn("f", &alignedBlocks[..], &[]), arena4);
811
    let over = [il::Layout { size: 8, alignment: 0x80000000, slots: &[], regions: 0 }];
812
    let mut capacity = false;
813
    try generateAll(alignedFns, &over[..]) catch err {
814
        let case rv64::Error::Capacity(limit) = err else {
815
            throw testing::TestError::Failed;
816
        };
817
        try testing::expect(limit == rv64::Limit::StackAlignment);
818
        set capacity = true;
819
    };
820
    try testing::expect(capacity);
821
}
822
823
/// State of the generator of random straight-line functions.
824
record Random {
825
    /// Current state of the linear congruential generator.
826
    state: u64,
827
}
828
829
/// The next random number below `bound`.
830
fn next(r: &mut Random, bound: u32) -> u32 {
831
    set r.state = r.state * 6364136223846793005 + 1442695040888963407;
832
    return ((r.state >> 33) % bound as u64) as u32;
833
}
834
835
/// Generate functions of random data operations, calls and jumps that pass many values, and
836
/// check that code generation accepts all of them.
837
@test unsafe fn randomFunctions() throws (testing::TestError) {
838
    let mut random = Random { state: 12345 };
839
    for _ in 0 .. 100 {
840
        let arena = heap::over(&mut SHAPE_STORAGE[..]);
841
        let mut blocks: *mut [il::Block] = &mut [];
842
        let mut vals: *mut [il::Val] = &mut [];
843
        let mut instrs: *mut [il::Instr] = &mut [];
844
        let mut params: *mut [il::Param] = &mut [];
845
        // Registers defined so far, which every later instruction can use.
846
        let mut defined: u32 = 0;
847
        // More values than registers are live, so that the spill pass runs. Its cost grows
848
        // steeply with the number of steps.
849
        let steps = 30 + next(&mut random, 10);
850
        for step in 0 .. steps {
851
            let kind = next(&mut random, 10);
852
            if defined < 2 or kind < 3 {
853
                push(
854
                    &mut instrs,
855
                    il::Instr::Copy {
856
                        dst: il::Reg { n: defined }, val: il::Val::Imm(step as i64)
857
                    },
858
                    arena
859
                );
860
                set defined += 1;
861
            } else if kind < 6 {
862
                push(
863
                    &mut instrs,
864
                    il::Instr::BinOp {
865
                        op: il::BinOp::Add,
866
                        typ: il::Type::W64,
867
                        dst: il::Reg { n: defined },
868
                        a: val(next(&mut random, defined)),
869
                        b: val(next(&mut random, defined)),
870
                    },
871
                    arena
872
                );
873
                set defined += 1;
874
            } else if kind < 8 {
875
                let count = next(&mut random, 12);
876
                let start = vals.len;
877
                for _ in 0 .. count {
878
                    try! vals.append(val(next(&mut random, defined)), arena);
879
                }
880
                let mut result: ?il::Reg = nil;
881
                if next(&mut random, 2) == 0 {
882
                    set result = il::Reg { n: defined };
883
                    set defined += 1;
884
                }
885
                push(
886
                    &mut instrs,
887
                    il::Instr::Call {
888
                        retTy: il::ValType::Data(il::Type::W64),
889
                        dst: result,
890
                        func: il::Val::FnAddr("target"),
891
                        args: il::ArgRange { start, len: count },
892
                    },
893
                    arena
894
                );
895
            } else {
896
                // Pass some of the values to a new block, which uses them as parameters.
897
                let count = 1 + next(&mut random, 8);
898
                let start = vals.len;
899
                let mut next_params: *mut [il::Param] = &mut [];
900
                for _ in 0 .. count {
901
                    try! vals.append(val(next(&mut random, defined)), arena);
902
                }
903
                for _ in 0 .. count {
904
                    try! next_params.append(
905
                        il::Param {
906
                            value: il::Reg { n: defined }, type: il::ValType::Data(il::Type::W64)
907
                        },
908
                        arena
909
                    );
910
                    set defined += 1;
911
                }
912
                push(
913
                    &mut instrs,
914
                    il::Instr::Jmp {
915
                        target: blocks.len + 1, args: il::ArgRange { start, len: count }
916
                    },
917
                    arena
918
                );
919
                try! blocks.append(
920
                    il::Block {
921
                        label: il::BlockLabel { base: "b", suffix: nil },
922
                        params: &params[..],
923
                        instrs: &instrs[..],
924
                        locs: &[],
925
                        preds: &[],
926
                        loopDepth: 0,
927
                    },
928
                    arena
929
                );
930
                set params = next_params;
931
                set instrs = &mut [];
932
            }
933
        }
934
        // Use every register once, so that all of them are live until the end.
935
        for i in 0 .. defined {
936
            push(
937
                &mut instrs,
938
                il::Instr::BinOp {
939
                    op: il::BinOp::Add,
940
                    typ: il::Type::W64,
941
                    dst: il::Reg { n: defined + i },
942
                    a: val(i),
943
                    b: val(next(&mut random, defined)),
944
                },
945
                arena
946
            );
947
        }
948
        push(&mut instrs, il::Instr::Ret { val: nil }, arena);
949
        try! blocks.append(
950
            il::Block {
951
                label: il::BlockLabel { base: "b", suffix: nil },
952
                params: &params[..],
953
                instrs: &instrs[..],
954
                locs: &[],
955
                preds: &[],
956
                loopDepth: 0,
957
            },
958
            arena
959
        );
960
        let mut funcs: *mut [il::Fn] = &mut [];
961
        try! funcs.append(target(arena), arena);
962
        try! funcs.append(voidFn("f", &blocks[..], &vals[..]), arena);
963
        try generateWith(funcs, &[], 64, 16) catch {
964
            throw testing::TestError::Failed;
965
        };
966
    }
967
}
968
969
/// With the stack check, a frame is checked against the limit in `tp` before the stack
970
/// pointer moves, and a call with stack arguments checks its outgoing area the same way.
971
@test unsafe fn stackCheck() throws (testing::TestError) {
972
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
973
    let mut instrs: *mut [il::Instr] = &mut [];
974
    push(&mut instrs, il::Instr::Reserve { dst: il::Reg { n: 0 }, layout: 0 }, arena);
975
    push(&mut instrs, il::Instr::Ret { val: nil }, arena);
976
    let mut blocks: *mut [il::Block] = &mut [];
977
    try! blocks.append(blockOf(&instrs[..]), arena);
978
    let mut funcs: *mut [il::Fn] = &mut [];
979
    try! funcs.append(voidFn("f", &blocks[..], &[]), arena);
980
    let layouts = [il::Layout { size: 8, alignment: 8, slots: &[], regions: 0 }];
981
    for checked in [false, true] {
982
        let storage = heap::over(&mut MEMORY[..]);
983
        let labelTables = try! tables(storage);
984
        let scratch = heap::over(&mut SHAPE_SCRATCH[..]);
985
        let mut generator = try! rv64::beginProgram(
986
            rv64::ProgramOptions {
987
                stack: rv64::StackCheck::TpLimit if checked else rv64::StackCheck::Off,
988
                entryPatch: rv64::EntryPatch::None,
989
                debug: false,
990
                placement: rv64::image::Placement::Hosted,
991
            },
992
            storage,
993
            labelTables
994
        );
995
        try! rv64::generateFunction(&mut generator, &funcs[0], &layouts[..], scratch);
996
        let code = &generator.e.code[..];
997
        // The frame is 16 bytes: 8 bytes of object, the return address and the frame pointer.
998
        let first = encode::addi(rv64::SP, rv64::SP, -32);
999
        if checked {
1000
            try testing::expect(code[0] == encode::sub(rv64::ADDR_SCRATCH, rv64::SP, rv64::TP));
1001
            try testing::expect(code[2] == encode::bgeu(rv64::ADDR_SCRATCH, rv64::SCRATCH1, 8));
1002
            try testing::expect(code[3] == encode::ebreak());
1003
            try testing::expect(code[4] == first);
1004
        } else {
1005
            try testing::expect(code[0] == first);
1006
        }
1007
    }
1008
}
1009
1010
//////////////////////////////
1011
// Register assignment order //
1012
//////////////////////////////
1013
1014
/// A data parameter of a block.
1015
fn dataParam(n: u32) -> il::Param {
1016
    return il::Param { value: il::Reg { n }, type: il::ValType::Data(il::Type::W64) };
1017
}
1018
1019
/// A jump without arguments.
1020
fn jumpTo(target: u32) -> il::Instr {
1021
    return il::Instr::Jmp { target, args: il::ArgRange { start: 0, len: 0 } };
1022
}
1023
1024
/// Values that are live together get different registers when a block is laid out before the
1025
/// block that defines a value it uses. The pointer `1` is defined in block 2, and used in
1026
/// block 1 beside the data `3`.
1027
@test unsafe fn layoutBeforeDefinition() throws (testing::TestError) {
1028
    let config = rv64::targetConfig();
1029
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
1030
    let mut entry: *mut [il::Instr] = &mut [];
1031
    push(&mut entry, jumpTo(2), arena);
1032
    let mut reader: *mut [il::Instr] = &mut [];
1033
    push(&mut reader, copyOf(3, 0x1000), arena);
1034
    push(
1035
        &mut reader,
1036
        il::Instr::Load {
1037
            typ: il::Type::W64, dst: il::Reg { n: 4 }, src: il::Reg { n: 1 }, offset: 0
1038
        },
1039
        arena
1040
    );
1041
    push(&mut reader, addOf(5, 4, 3), arena);
1042
    push(&mut reader, il::Instr::Ret { val: val(5) }, arena);
1043
    let mut writer: *mut [il::Instr] = &mut [];
1044
    push(&mut writer, copyOf(0, 5), arena);
1045
    push(&mut writer, il::Instr::Reserve { dst: il::Reg { n: 1 }, layout: 0 }, arena);
1046
    push(&mut writer, addOf(2, 0, 0), arena);
1047
    push(&mut writer, jumpTo(1), arena);
1048
    let mut blocks: *mut [il::Block] = &mut [];
1049
    try! blocks.append(blockOf(&entry[..]), arena);
1050
    try! blocks.append(blockOf(&reader[..]), arena);
1051
    try! blocks.append(blockOf(&writer[..]), arena);
1052
    let mut funcs: *mut [il::Fn] = &mut [];
1053
    try! funcs.append(
1054
        il::Fn {
1055
            name: "f",
1056
            params: &[],
1057
            returnType: il::ValType::Data(il::Type::W64),
1058
            isExtern: false,
1059
            isLeaf: true,
1060
            blocks: &blocks[..],
1061
            vals: &[],
1062
            cases: &[],
1063
            borrows: &[],
1064
        },
1065
        arena
1066
    );
1067
    let result = try regalloc::allocate(&funcs[0], &config, arena) catch {
1068
        throw testing::TestError::Failed;
1069
    };
1070
    let pointer = result.assignments[1] else {
1071
        throw testing::TestError::Failed;
1072
    };
1073
    let data = result.assignments[3] else {
1074
        throw testing::TestError::Failed;
1075
    };
1076
    try testing::expect(*pointer <> *data);
1077
}
1078
1079
/// Blocks that the entry block cannot reach are assigned too, and a register is not shared by
1080
/// two values of one such block.
1081
@test unsafe fn unreachableBlocks() throws (testing::TestError) {
1082
    let config = rv64::targetConfig();
1083
    let arena = heap::over(&mut SHAPE_STORAGE[..]);
1084
    let mut entry: *mut [il::Instr] = &mut [];
1085
    push(&mut entry, il::Instr::Ret { val: nil }, arena);
1086
    let mut first: *mut [il::Instr] = &mut [];
1087
    push(&mut first, copyOf(0, 1), arena);
1088
    push(&mut first, copyOf(1, 2), arena);
1089
    push(&mut first, jumpTo(2), arena);
1090
    let mut second: *mut [il::Instr] = &mut [];
1091
    push(&mut second, copyOf(2, 3), arena);
1092
    push(&mut second, addOf(3, 2, 2), arena);
1093
    push(&mut second, il::Instr::Ret { val: val(3) }, arena);
1094
    let mut blocks: *mut [il::Block] = &mut [];
1095
    try! blocks.append(blockOf(&entry[..]), arena);
1096
    try! blocks.append(blockOf(&first[..]), arena);
1097
    try! blocks.append(blockOf(&second[..]), arena);
1098
    let mut funcs: *mut [il::Fn] = &mut [];
1099
    try! funcs.append(
1100
        il::Fn {
1101
            name: "f",
1102
            params: &[],
1103
            returnType: il::ValType::Data(il::Type::W64),
1104
            isExtern: false,
1105
            isLeaf: true,
1106
            blocks: &blocks[..],
1107
            vals: &[],
1108
            cases: &[],
1109
            borrows: &[],
1110
        },
1111
        arena
1112
    );
1113
    let result = try regalloc::allocate(&funcs[0], &config, arena) catch {
1114
        throw testing::TestError::Failed;
1115
    };
1116
    let live = try! regalloc::liveness::analyze(&funcs[0], arena);
1117
    try testing::expect(allocationConflicts(&funcs[0], &result, &live, arena) == 0);
1118
    for n in 0 .. 4 {
1119
        try testing::expect(result.assignments[n] <> nil);
1120
    }
1121
}
1122
1123
/// Most blocks of a generated function.
1124
constant GEN_BLOCKS: u32 = 8;
1125
/// Number of generated functions per layout.
1126
constant GEN_SEEDS: u32 = 30;
1127
1128
/// State of a generated function. Blocks form a dominator tree, so each block uses only
1129
/// values of its ancestors and its own.
1130
record Cfg {
1131
    /// Source of random numbers.
1132
    random: Random,
1133
    /// Number of blocks.
1134
    count: u32,
1135
    /// Dominator tree parent of each block, in tree numbering.
1136
    parent: [u32; 8],
1137
    /// Dominator tree children of each block.
1138
    kids: [[u32; 8]; 8],
1139
    /// Number of children of each block.
1140
    kidCount: [u32; 8],
1141
    /// Position of each block in the layout.
1142
    place: [u32; 8],
1143
    /// First register of the parameters of each block.
1144
    paramStart: [u32; 8],
1145
    /// Number of parameters of each block.
1146
    paramCount: [u32; 8],
1147
    /// Values that each block can use.
1148
    avail: [[u32; 200]; 8],
1149
    /// Number of values that each block can use.
1150
    availLen: [u32; 8],
1151
    /// Number of registers used so far.
1152
    regs: u32,
1153
}
1154
1155
/// A random value that block `b` can use.
1156
fn pickAvail(c: &mut Cfg, b: u32) -> u32 {
1157
    let n = next(&mut c.random, c.availLen[b]);
1158
    return c.avail[b][n];
1159
}
1160
1161
/// Make register `r` usable in block `b`.
1162
fn addAvail(c: &mut Cfg, b: u32, r: u32) {
1163
    set c.avail[b][c.availLen[b]] = r;
1164
    set c.availLen[b] += 1;
1165
}
1166
1167
/// Append arguments for the parameters of block `t`, taken from the values of block `b`.
1168
fn edgeArgs(
1169
    c: &mut Cfg, b: u32, t: u32, vals: &mut *mut [il::Val], arena: &heap::Heap
1170
) -> il::ArgRange {
1171
    let start = vals.len;
1172
    for _ in 0 .. c.paramCount[t] {
1173
        try! vals.append(val(pickAvail(c, b)), arena);
1174
    }
1175
    return il::ArgRange { start, len: c.paramCount[t] };
1176
}
1177
1178
/// Whether block `x` is block `y` or one of its dominators.
1179
fn dominates(c: &Cfg, x: u32, y: u32) -> bool {
1180
    let mut z = y;
1181
    loop {
1182
        if z == x {
1183
            return true;
1184
        }
1185
        if z == 0 {
1186
            return false;
1187
        }
1188
        set z = c.parent[z];
1189
    }
1190
}
1191
1192
/// A random jump target for block `b`, whose parameter values can be passed from `b`: the
1193
/// target's dominator is `b` or one of its dominators.
1194
fn anyTarget(c: &mut Cfg, b: u32) -> u32 {
1195
    for _ in 0 .. 8 {
1196
        let t = next(&mut c.random, c.count);
1197
        if t == 0 or dominates(c, c.parent[t], b) {
1198
            return t;
1199
        }
1200
    }
1201
    return b;
1202
}
1203
1204
/// A jump from block `b` to block `t`, in tree numbering.
1205
fn jumpWith(
1206
    c: &mut Cfg, b: u32, t: u32, vals: &mut *mut [il::Val], arena: &heap::Heap
1207
) -> il::Instr {
1208
    let args = edgeArgs(c, b, t, vals, arena);
1209
    return il::Instr::Jmp { target: c.place[t], args };
1210
}
1211
1212
/// Generate a function with random data operations, calls and branches. The dominator tree is
1213
/// random. With `shuffle`, the layout is a random permutation that keeps only the entry block
1214
/// first, so a block can come before the blocks that dominate it.
1215
fn genFn(seed: u64, shuffle: bool, arena: &heap::Heap) -> il::Fn {
1216
    let mut c = Cfg {
1217
        random: Random { state: seed },
1218
        count: 0,
1219
        parent: [0; 8],
1220
        kids: [[0; 8]; 8],
1221
        kidCount: [0; 8],
1222
        place: [0; 8],
1223
        paramStart: [0; 8],
1224
        paramCount: [0; 8],
1225
        avail: [[0; 200]; 8],
1226
        availLen: [0; 8],
1227
        regs: 0,
1228
    };
1229
    set c.count = 2 + next(&mut c.random, GEN_BLOCKS - 1);
1230
    for b in 0 .. c.count {
1231
        set c.place[b] = b;
1232
    }
1233
    if shuffle {
1234
        let mut i = c.count - 1;
1235
        while i > 1 {
1236
            let j = 1 + next(&mut c.random, i);
1237
            let swap = c.place[i];
1238
            set c.place[i] = c.place[j];
1239
            set c.place[j] = swap;
1240
            set i -= 1;
1241
        }
1242
    }
1243
    for b in 1 .. c.count {
1244
        let p = next(&mut c.random, b);
1245
        set c.parent[b] = p;
1246
        set c.kids[p][c.kidCount[p]] = b;
1247
        set c.kidCount[p] += 1;
1248
        set c.paramCount[b] = next(&mut c.random, 4);
1249
        set c.paramStart[b] = c.regs;
1250
        set c.regs += c.paramCount[b];
1251
    }
1252
    let mut vals: *mut [il::Val] = &mut [];
1253
    let mut cases: *mut [il::SwitchCase] = &mut [];
1254
    let mut done: [il::Block; 8] = [blockOf(&[]); 8];
1255
    for b in 0 .. c.count {
1256
        if b > 0 {
1257
            let p = c.parent[b];
1258
            for i in 0 .. c.availLen[p] {
1259
                let v = c.avail[p][i];
1260
                addAvail(&mut c, b, v);
1261
            }
1262
            for k in 0 .. c.paramCount[b] {
1263
                let v = c.paramStart[b] + k;
1264
                addAvail(&mut c, b, v);
1265
            }
1266
        }
1267
        let mut instrs: *mut [il::Instr] = &mut [];
1268
        let mut n = 1 + next(&mut c.random, 7);
1269
        if seed % 3 == 0 {
1270
            set n = 10 + next(&mut c.random, 40);
1271
        }
1272
        for _ in 0 .. n {
1273
            let kind = next(&mut c.random, 10);
1274
            if c.availLen[b] < 2 or kind < 3 {
1275
                let r = c.regs;
1276
                set c.regs += 1;
1277
                push(&mut instrs, copyOf(r, 1 + next(&mut c.random, 100) as i64), arena);
1278
                addAvail(&mut c, b, r);
1279
            } else if kind < 6 {
1280
                let r = c.regs;
1281
                set c.regs += 1;
1282
                let x = pickAvail(&mut c, b);
1283
                let y = pickAvail(&mut c, b);
1284
                push(&mut instrs, addOf(r, x, y), arena);
1285
                addAvail(&mut c, b, r);
1286
            } else if kind < 8 {
1287
                let count = next(&mut c.random, 11);
1288
                let start = vals.len;
1289
                for _ in 0 .. count {
1290
                    try! vals.append(val(pickAvail(&mut c, b)), arena);
1291
                }
1292
                let mut result: ?il::Reg = nil;
1293
                if next(&mut c.random, 2) == 0 {
1294
                    set result = il::Reg { n: c.regs };
1295
                }
1296
                push(
1297
                    &mut instrs,
1298
                    il::Instr::Call {
1299
                        retTy: il::ValType::Data(il::Type::W64),
1300
                        dst: result,
1301
                        func: il::Val::FnAddr("target"),
1302
                        args: il::ArgRange { start, len: count },
1303
                    },
1304
                    arena
1305
                );
1306
                if let r = result {
1307
                    addAvail(&mut c, b, r.n);
1308
                    set c.regs += 1;
1309
                }
1310
            } else {
1311
                // A result that nothing uses, which extends the live ranges of its operands.
1312
                let r = c.regs;
1313
                set c.regs += 1;
1314
                let x = pickAvail(&mut c, b);
1315
                let y = pickAvail(&mut c, b);
1316
                push(&mut instrs, addOf(r, x, y), arena);
1317
            }
1318
        }
1319
        let kc = c.kidCount[b];
1320
        if kc == 0 {
1321
            if next(&mut c.random, 3) == 0 {
1322
                push(&mut instrs, il::Instr::Ret { val: nil }, arena);
1323
            } else {
1324
                let t = anyTarget(&mut c, b);
1325
                push(&mut instrs, jumpWith(&mut c, b, t, &mut vals, arena), arena);
1326
            }
1327
        } else if kc == 1 {
1328
            let k0 = c.kids[b][0];
1329
            let r = next(&mut c.random, 3);
1330
            if r == 0 {
1331
                push(&mut instrs, jumpWith(&mut c, b, k0, &mut vals, arena), arena);
1332
            } else {
1333
                let mut other = anyTarget(&mut c, b);
1334
                if r == 2 {
1335
                    set other = k0;
1336
                }
1337
                let thenArgs = edgeArgs(&mut c, b, k0, &mut vals, arena);
1338
                let elseArgs = edgeArgs(&mut c, b, other, &mut vals, arena);
1339
                push(
1340
                    &mut instrs,
1341
                    il::Instr::Br {
1342
                        op: il::CmpOp::Eq,
1343
                        typ: il::Type::W64,
1344
                        a: val(pickAvail(&mut c, b)),
1345
                        b: il::Val::Imm(0),
1346
                        thenTarget: c.place[k0],
1347
                        thenArgs,
1348
                        elseTarget: c.place[other],
1349
                        elseArgs,
1350
                    },
1351
                    arena
1352
                );
1353
            }
1354
        } else if kc == 2 {
1355
            let k0 = c.kids[b][0];
1356
            let k1 = c.kids[b][1];
1357
            let thenArgs = edgeArgs(&mut c, b, k0, &mut vals, arena);
1358
            let elseArgs = edgeArgs(&mut c, b, k1, &mut vals, arena);
1359
            push(
1360
                &mut instrs,
1361
                il::Instr::Br {
1362
                    op: il::CmpOp::Eq,
1363
                    typ: il::Type::W64,
1364
                    a: val(pickAvail(&mut c, b)),
1365
                    b: il::Val::Imm(0),
1366
                    thenTarget: c.place[k0],
1367
                    thenArgs,
1368
                    elseTarget: c.place[k1],
1369
                    elseArgs,
1370
                },
1371
                arena
1372
            );
1373
        } else {
1374
            let start = cases.len;
1375
            for i in 0 .. kc - 1 {
1376
                let k = c.kids[b][i];
1377
                let args = edgeArgs(&mut c, b, k, &mut vals, arena);
1378
                try! cases.append(
1379
                    il::SwitchCase {
1380
                        value: i as i64, target: c.place[k], args
1381
                    },
1382
                    arena
1383
                );
1384
            }
1385
            // The same target again, with other arguments.
1386
            let k = c.kids[b][0];
1387
            let args = edgeArgs(&mut c, b, k, &mut vals, arena);
1388
            try! cases.append(il::SwitchCase { value: 99, target: c.place[k], args }, arena);
1389
            let last = c.kids[b][kc - 1];
1390
            let defaultArgs = edgeArgs(&mut c, b, last, &mut vals, arena);
1391
            push(
1392
                &mut instrs,
1393
                il::Instr::Switch {
1394
                    val: val(pickAvail(&mut c, b)),
1395
                    defaultTarget: c.place[last],
1396
                    defaultArgs,
1397
                    cases: il::CaseRange { start, len: kc },
1398
                },
1399
                arena
1400
            );
1401
        }
1402
        let mut params: *mut [il::Param] = &mut [];
1403
        for k in 0 .. c.paramCount[b] {
1404
            try! params.append(dataParam(c.paramStart[b] + k), arena);
1405
        }
1406
        set done[c.place[b]] = il::Block {
1407
            label: il::BlockLabel { base: "b", suffix: nil },
1408
            params: &params[..],
1409
            instrs: &instrs[..],
1410
            locs: &[],
1411
            preds: &[],
1412
            loopDepth: 0,
1413
        };
1414
    }
1415
    let mut blocks: *mut [il::Block] = &mut [];
1416
    for i in 0 .. c.count {
1417
        try! blocks.append(done[i], arena);
1418
    }
1419
    return il::Fn {
1420
        name: "f",
1421
        params: &[],
1422
        returnType: il::ValType::Void,
1423
        isExtern: false,
1424
        isLeaf: false,
1425
        blocks: &blocks[..],
1426
        vals: &vals[..],
1427
        cases: &cases[..],
1428
        borrows: &[],
1429
    };
1430
}
1431
1432
/// Count the values of `members` that share a physical register with an earlier value, plus
1433
/// the values that have none. With a nonzero `calleeOnly`, a value whose register is not in
1434
/// that mask also counts.
1435
fn conflicts(members: &bitset::Bitset, r: &regalloc::AllocResult, calleeOnly: u32) -> u32 {
1436
    let mut taken: u32 = 0;
1437
    let mut bad: u32 = 0;
1438
    let mut it = bitset::iter(members);
1439
    while let x = bitset::iterNext(members, &mut it) {
1440
        if regalloc::spill::isSpilled(&r.spill, il::Reg { n: x }) {
1441
            continue;
1442
        }
1443
        let phys = r.assignments[x] else {
1444
            set bad += 1;
1445
            continue;
1446
        };
1447
        let bit: u32 = 1 << *phys as u32;
1448
        if (taken & bit) <> 0 or (calleeOnly <> 0 and (calleeOnly & bit) == 0) {
1449
            set bad += 1;
1450
        }
1451
        set taken |= bit;
1452
    }
1453
    return bad;
1454
}
1455
1456
/// Count the conflicts in an allocation: values that are live together and share a register,
1457
/// and values that are live across a call outside the callee-saved registers.
1458
fn allocationConflicts(
1459
    func: *il::Fn,
1460
    r: &regalloc::AllocResult,
1461
    live: &regalloc::liveness::LiveInfo,
1462
    a: &heap::Heap
1463
) -> u32 {
1464
    let mut calleeSaved: u32 = 0;
1465
    for s in rv64::CALLEE_SAVED {
1466
        set calleeSaved |= 1 << *s as u32;
1467
    }
1468
    let mut bad: u32 = 0;
1469
    let mut cur = try! bitset::allocate(a, live.maxReg);
1470
    let mut tmp = try! bitset::allocate(a, live.maxReg);
1471
    for b in 0 .. func.blocks.len {
1472
        let block = &func.blocks[b];
1473
        bitset::copy(&mut cur, &live.liveOut[b]);
1474
        let mut i = block.instrs.len;
1475
        while i > 0 {
1476
            set i -= 1;
1477
            let instr = block.instrs[i];
1478
            bitset::copy(&mut tmp, &cur);
1479
            if let dst = il::instrDst(&instr) {
1480
                bitset::put(&mut tmp, dst.n);
1481
            }
1482
            set bad += conflicts(&tmp, r, 0);
1483
            if il::isCall(&instr) {
1484
                bitset::copy(&mut tmp, &cur);
1485
                if let dst = il::instrDst(&instr) {
1486
                    bitset::clear(&mut tmp, dst.n);
1487
                }
1488
                set bad += conflicts(&tmp, r, calleeSaved);
1489
            }
1490
            if let dst = il::instrDst(&instr) {
1491
                bitset::clear(&mut cur, dst.n);
1492
            }
1493
            il::forEachReg(func, &instr, &mut cur);
1494
            bitset::copy(&mut tmp, &cur);
1495
            set bad += conflicts(&tmp, r, 0);
1496
        }
1497
        bitset::copy(&mut tmp, &cur);
1498
        for p in block.params {
1499
            bitset::put(&mut tmp, p.value.n);
1500
        }
1501
        set bad += conflicts(&tmp, r, 0);
1502
    }
1503
    return bad;
1504
}
1505
1506
/// Allocate generated functions, in dominance order and in shuffled layouts. No two values that
1507
/// are live together share a register, and values live across a call are callee-saved.
1508
@test unsafe fn randomLayouts() throws (testing::TestError) {
1509
    let config = rv64::targetConfig();
1510
    for shuffle in [false, true] {
1511
        for seed in 1 .. GEN_SEEDS + 1 {
1512
            let arena = heap::over(&mut SHAPE_STORAGE[..]);
1513
            let func = genFn(seed as u64 * 7919, shuffle, arena);
1514
            let mut funcs: *mut [il::Fn] = &mut [];
1515
            try! funcs.append(func, arena);
1516
            let work = heap::over(&mut SHAPE_SCRATCH[..]);
1517
            let live = try! regalloc::liveness::analyze(&funcs[0], work);
1518
            let result = try regalloc::allocate(&funcs[0], &config, work) catch {
1519
                throw testing::TestError::Failed;
1520
            };
1521
            try testing::expect(allocationConflicts(&funcs[0], &result, &live, work) == 0);
1522
        }
1523
    }
1524
}
1525
1526
/// Dense switches retain edge arguments and case order in short and full tables.
1527
@test unsafe fn denseSwitch() throws (testing::TestError) {
1528
    for count in [16, 1024] {
1529
        let arena = heap::over(&mut SHAPE_STORAGE[..]);
1530
        let mut cases: *mut [il::SwitchCase] = &mut [];
1531
        for i in 0 .. count {
1532
            try! cases.append(
1533
                il::SwitchCase {
1534
                    value: i as i64 - 8, target: 1, args: il::ArgRange { start: i, len: 1 }
1535
                },
1536
                arena
1537
            );
1538
        }
1539
        try! cases.append(
1540
            il::SwitchCase {
1541
                value: -8, target: 1, args: il::ArgRange { start: count, len: 1 }
1542
            },
1543
            arena
1544
        );
1545
        let mut vals: *mut [il::Val] = &mut [];
1546
        for i in 0 .. count + 1 {
1547
            try! vals.append(il::Val::Imm(i as i64), arena);
1548
        }
1549
        let mut blocks: *mut [il::Block] = &mut [];
1550
        let mut entry: *mut [il::Instr] = &mut [];
1551
        push(
1552
            &mut entry,
1553
            il::Instr::Switch {
1554
                val: val(0),
1555
                defaultTarget: 1,
1556
                defaultArgs: il::ArgRange { start: count, len: 1 },
1557
                cases: il::CaseRange { start: 0, len: count + 1 },
1558
            },
1559
            arena
1560
        );
1561
        try! blocks.append(blockOf(&entry[..]), arena);
1562
        let mut instrs: *mut [il::Instr] = &mut [];
1563
        push(&mut instrs, il::Instr::Ret { val: val(1) }, arena);
1564
        let mut done = blockOf(&instrs[..]);
1565
        let mut params: *mut [il::Param] = &mut [];
1566
        try! params.append(dataParam(1), arena);
1567
        set done.params = &params[..];
1568
        try! blocks.append(done, arena);
1569
        let mut func = voidFn("f", &blocks[..], &vals[..]);
1570
        let mut inputs: *mut [il::Param] = &mut [];
1571
        try! inputs.append(dataParam(0), arena);
1572
        set func.params = &inputs[..];
1573
        set func.returnType = il::ValType::Data(il::Type::W64);
1574
        set func.cases = &cases[..];
1575
        let storage = heap::over(&mut MEMORY[..]);
1576
        let labelTables = try! tables(storage);
1577
        let scratch = heap::over(&mut SHAPE_SCRATCH[..]);
1578
        let mut generator = try! rv64::beginProgram(
1579
            rv64::ProgramOptions {
1580
                stack: rv64::StackCheck::Off,
1581
                entryPatch: rv64::EntryPatch::None,
1582
                debug: false,
1583
                placement: rv64::image::Placement::Hosted,
1584
            },
1585
            storage,
1586
            labelTables
1587
        );
1588
        let mut funcs: *mut [il::Fn] = &mut [];
1589
        try! funcs.append(func, arena);
1590
        try! rv64::generateFunction(&mut generator, &funcs[0], &[], scratch);
1591
        let mut indexed = false;
1592
        for word, i in &generator.e.code[..] {
1593
            if word == encode::jalr(rv64::ZERO, rv64::SCRATCH1, 12) {
1594
                set indexed = true;
1595
                // The first case for each value owns its argument edge.
1596
                for slot in 0 .. count {
1597
                    let at = i + 1 + slot;
1598
                    let offset = labels::branchToBlock(
1599
                        &generator.e.labels, at, 4 + slot, rv64::INSTR_SIZE
1600
                    );
1601
                    assert generator.e.code[at] == encode::jal(rv64::ZERO, offset);
1602
                }
1603
            }
1604
        }
1605
        assert indexed;
1606
    }
1607
}