.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
rv64/
asm/
image/
shared/
tests/
atomics.rad
4.9 KiB
bounds.rad
57.3 KiB
asm.rad
32.4 KiB
atomics.rad
5.1 KiB
decode.rad
27.1 KiB
emit.rad
34.6 KiB
encode.rad
30.9 KiB
image.rad
6.1 KiB
isel.rad
138.3 KiB
printer.rad
19.2 KiB
shared.rad
21.1 KiB
tests.rad
73.3 KiB
vector.rad
59.4 KiB
rv64.rad
22.4 KiB
bits/
char/
collections/
fs/
hash/
lang/
mem/
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/arch/rv64/tests/bounds.rad
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: ¶ms[..], |
| 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: ¶ms[..], |
| 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", ©Blocks[..], &[]), 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: ¶ms[..], |
| 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: ¶ms[..], |
| 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: ¶ms[..], |
| 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: ®alloc::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: ®alloc::AllocResult, |
| 1461 | live: ®alloc::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 = ¶ms[..]; |
| 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 | } |