rv64: Emit single-instruction conditional branches

adb500c32b8847f2a605ad2546c5d3db25f6a64f994b17339d8a6aa731a35547
Every conditional branch reserved two instructions, so that a target
beyond the 4 KiB range of a B-type branch could use an inverted branch
over a `jal`. Branches that reach their target, nearly all of them, left
the second slot as a `nop`, which ran on every fall-through, including
each iteration of most loops.

Conditional branches are now a single instruction. When patching finds
one that does not reach its target, it marks the branch by its position
in the list of pending branches, the emitter rewinds to the start of the
function body, and `selectFn` emits the body again with the marked
branches in the long form. Selection is deterministic, so a position
names the same branch each time, and long forms only lengthen the body,
so each emission marks at least one more branch.

Only functions with a branch beyond 4 KiB are emitted twice. Rewinding
avoids compacting emitted code, which would have to update every
recorded code index and relative offset. Together with the previous
commit, the prog.* fixtures run 6.6% fewer instructions (geometric
mean), and the compiler takes slightly fewer instructions to compile
itself.

Assisted-by: Claude:opus-5.5
Alexis Sellier committed ago 1 parent a6cd53fc
lib/std/arch/rv64/emit.rad +99 -14
38 38
    index: u32,
39 39
    /// Target block index.
40 40
    target: u32,
41 41
    /// Type of branch for re-encoding.
42 42
    kind: BranchKind,
43 +
    /// Whether a conditional branch is an inverted B-type branch over a J-type
44 +
    /// jump, within 1 MiB of its target, instead of a B-type branch within 4 KiB.
45 +
    long: bool,
46 +
}
47 +
48 +
/// Lengths of the emitter lists at the start of a function body, so that the
49 +
/// body can be emitted again.
50 +
export record Mark: Copy {
51 +
    /// Number of instructions.
52 +
    code: u32,
53 +
    /// Number of pending calls.
54 +
    calls: u32,
55 +
    /// Number of pending assembly jumps.
56 +
    jumps: u32,
57 +
    /// Number of pending address loads.
58 +
    addrLoads: u32,
59 +
    /// Number of debug entries.
60 +
    debugEntries: u32,
43 61
}
44 62
45 63
/// Type of branch instruction.
46 64
export union BranchKind: Copy {
47 65
    /// Conditional branch (B-type encoding).
113 131
    stackCheck: bool,
114 132
    /// Emitted instructions storage.
115 133
    code: *mut [u32],
116 134
    /// Local branches needing offset patching.
117 135
    pendingBranches: *mut [PendingBranch],
136 +
    /// Whether the local branch at each position of `pendingBranches` uses the
137 +
    /// long form. Local branches are recorded in the same order each time a
138 +
    /// function body is emitted, so a position names the same branch.
139 +
    longBranches: *mut [bool],
118 140
    /// Function calls needing offset patching.
119 141
    pendingCalls: *mut [PendingCall],
120 142
    /// Assembly jumps needing offset patching.
121 143
    pendingJumps: *mut [PendingJump],
122 144
    /// Function address loads needing offset patching.
201 223
    let mut arena = arena;
202 224
    let mut code: *mut [u32] = &mut [];
203 225
    try code.reserve(MAX_INSTRS, &mut arena);
204 226
    let mut pendingBranches: *mut [PendingBranch] = &mut [];
205 227
    try pendingBranches.reserve(MAX_PENDING, &mut arena);
228 +
    let mut longBranches: *mut [bool] = &mut [];
229 +
    try longBranches.reserve(MAX_PENDING, &mut arena);
206 230
    let mut pendingCalls: *mut [PendingCall] = &mut [];
207 231
    try pendingCalls.reserve(MAX_PENDING, &mut arena);
208 232
    let mut pendingJumps: *mut [PendingJump] = &mut [];
209 233
    try pendingJumps.reserve(MAX_PENDING, &mut arena);
210 234
    let mut pendingAddrLoads: *mut [PendingAddrLoad] = &mut [];
220 244
        arena,
221 245
        sharedData: false,
222 246
        stackCheck: false,
223 247
        code,
224 248
        pendingBranches,
249 +
        longBranches,
225 250
        pendingCalls,
226 251
        pendingJumps,
227 252
        pendingAddrLoads,
228 253
        labels,
229 254
        funcs,
298 323
    };
299 324
}
300 325
301 326
/// Record a local branch needing later patching.
302 327
/// Unconditional jumps use a single slot (J-type, +-1MB range).
303 -
/// Conditional branches use two slots (B-type has only +-4KB range,
304 -
/// so large functions may need the inverted-branch + JAL fallback).
328 +
/// Conditional branches use one slot (B-type, +-4KB range), or two for the
329 +
/// inverted-branch + JAL form when an earlier emission of the function found
330 +
/// that the branch does not reach its target.
305 331
export fn recordBranch(e: &mut Emitter, targetBlock: u32, kind: BranchKind) throws (super::Error) {
332 +
    let position = e.pendingBranches.len;
333 +
    let long = position < e.longBranches.len and e.longBranches[position];
306 334
    try e.pendingBranches.append(
307 335
        PendingBranch {
308 336
            index: e.code.len,
309 337
            target: targetBlock,
310 338
            kind: kind,
339 +
            long,
311 340
        },
312 341
        &mut e.arena
313 342
    ) catch {
314 343
        throw super::Error::Allocation;
315 344
    };
316 -
    try emit(e, encode::nop()); // First slot, always needed.
317 -
318 -
    match kind {
319 -
        case BranchKind::Jump => {}
320 -
        else                  => try emit(e, encode::nop()), // Second slot for conditional branches.
345 +
    try emit(e, encode::nop());
346 +
    if long {
347 +
        try emit(e, encode::nop());
321 348
    }
322 349
}
323 350
324 351
/// Record a function call needing later patching.
325 352
/// Emits placeholder instructions that will be patched later.
413 440
        try emit(e, encode::nop()); // Package offset addition.
414 441
        try emit(e, encode::nop()); // Package offset low bits.
415 442
    }
416 443
}
417 444
445 +
/// Return the list lengths at the start of a function body, and forget which
446 +
/// local branches of the previous function use the long form.
447 +
export fn beginBody(e: &mut Emitter) -> Mark {
448 +
    let mut longBranches = e.longBranches.take();
449 +
    set e.longBranches = &mut longBranches[..0];
450 +
    return Mark {
451 +
        code: e.code.len,
452 +
        calls: e.pendingCalls.len,
453 +
        jumps: e.pendingJumps.len,
454 +
        addrLoads: e.pendingAddrLoads.len,
455 +
        debugEntries: e.debugEntries.len,
456 +
    };
457 +
}
458 +
459 +
/// Discard everything emitted for a function body since `mark`, keeping the
460 +
/// long-form choices of its local branches for the next emission.
461 +
export fn rewind(e: &mut Emitter, mark: Mark) {
462 +
    let mut code = e.code.take();
463 +
    set e.code = &mut code[..mark.code];
464 +
    let mut branches = e.pendingBranches.take();
465 +
    set e.pendingBranches = &mut branches[..0];
466 +
    let mut calls = e.pendingCalls.take();
467 +
    set e.pendingCalls = &mut calls[..mark.calls];
468 +
    let mut jumps = e.pendingJumps.take();
469 +
    set e.pendingJumps = &mut jumps[..mark.jumps];
470 +
    let mut addrLoads = e.pendingAddrLoads.take();
471 +
    set e.pendingAddrLoads = &mut addrLoads[..mark.addrLoads];
472 +
    let mut debugEntries = e.debugEntries.take();
473 +
    set e.debugEntries = &mut debugEntries[..mark.debugEntries];
474 +
}
475 +
418 476
/// Patch local branches and clear the pending list.
419 477
///
420 478
/// Called after each function.
421 479
///
422 -
/// Uses two-instruction sequences: short branches use `branch` and `nop`,
423 -
/// long branches use inverted branch  and `jal` or `auipc` and `jalr`.
424 -
export fn patchLocalBranches(e: &mut Emitter) throws (super::Error) {
480 +
/// Returns false when a short conditional branch does not reach its target.
481 +
/// Every such branch is then marked to use the long form, and the caller emits
482 +
/// the function body again after [`rewind`]. Long-form branches only make the
483 +
/// body longer, so each failed emission marks at least one more branch.
484 +
///
485 +
/// Short branches are a single B-type instruction. Long branches use an
486 +
/// inverted branch over a `jal`.
487 +
export fn patchLocalBranches(e: &mut Emitter) -> bool throws (super::Error) {
488 +
    let mut reaches = true;
489 +
    for position in 0..e.pendingBranches.len {
490 +
        let p = e.pendingBranches[position];
491 +
        if p.long {
492 +
            continue;
493 +
        }
494 +
        if let case BranchKind::Jump = p.kind {
495 +
            continue;
496 +
        }
497 +
        let offset = labels::branchToBlock(&e.labels, p.index, p.target, super::INSTR_SIZE);
498 +
        if not encode::isBranchImm(offset) {
499 +
            if e.longBranches.len <= position {
500 +
                try e.longBranches.resize(position + 1, false, &mut e.arena) catch {
501 +
                    throw super::Error::Allocation;
502 +
                };
503 +
            }
504 +
            set e.longBranches[position] = true;
505 +
            set reaches = false;
506 +
        }
507 +
    }
508 +
    if not reaches {
509 +
        return false;
510 +
    }
425 511
    // Patch from the last entry and remove it, so the list is empty on return.
426 512
    while e.pendingBranches.len > 0 {
427 513
        let p = e.pendingBranches[e.pendingBranches.len - 1];
428 514
        let offset = labels::branchToBlock(&e.labels, p.index, p.target, super::INSTR_SIZE);
429 515
        match p.kind {
430 516
            case BranchKind::Cond { op, rs1, rs2 } => {
431 -
                if encode::isBranchImm(offset) {
517 +
                if not p.long {
432 518
                    patch(e, p.index, encodeCondBranch(op, rs1, rs2, offset));
433 -
                    patch(e, p.index + 1, encode::nop());
434 519
                } else {
435 520
                    let adj = offset - super::INSTR_SIZE;
436 521
                    if not encode::isJumpImm(adj) {
437 522
                        throw super::Error::Relocation;
438 523
                    }
439 524
                    patch(e, p.index, encodeInvertedBranch(op, rs1, rs2, super::INSTR_SIZE * 2));
440 525
                    patch(e, p.index + 1, encode::jal(super::ZERO, adj));
441 526
                }
442 527
            }
443 528
            case BranchKind::InvertedCond { op, rs1, rs2 } => {
444 -
                if encode::isBranchImm(offset) {
529 +
                if not p.long {
445 530
                    patch(e, p.index, encodeInvertedBranch(op, rs1, rs2, offset));
446 -
                    patch(e, p.index + 1, encode::nop());
447 531
                } else {
448 532
                    let adj = offset - super::INSTR_SIZE;
449 533
                    if not encode::isJumpImm(adj) {
450 534
                        throw super::Error::Relocation;
451 535
                    }
461 545
                patch(e, p.index, encode::jal(super::ZERO, offset));
462 546
            }
463 547
        }
464 548
        e.pendingBranches.delete(e.pendingBranches.len - 1);
465 549
    }
550 +
    return true;
466 551
}
467 552
468 553
/// Encode a conditional branch instruction.
469 554
fn encodeCondBranch(op: il::CmpOp, rs1: gen::Reg, rs2: gen::Reg, offset: i32) -> u32 {
470 555
    match op {
lib/std/arch/rv64/isel.rad +30 -11
552 552
    e: &mut emit::Emitter,
553 553
    ralloc: regalloc::AllocResult,
554 554
    func: *il::Fn,
555 555
    layouts: &[il::Layout]
556 556
) throws (super::Error) {
557 -
    // Reset block offsets for this function.
558 -
    labels::resetBlocks(&mut e.labels);
559 557
    // Pre-scan the reserves to give them fixed frame slots.
560 558
    let reserved = try reserveSize(func, layouts);
561 559
    if reserved > I32_MAX as i32 - ralloc.spill.frameSize {
562 560
        throw super::Error::Capacity;
563 561
    }
567 565
        ralloc.spill.frameSize + reserved,
568 566
        ralloc.usedCalleeSaved,
569 567
        func.blocks.len,
570 568
        isLeaf
571 569
    );
570 +
    // Record function name for printing.
571 +
    try emit::recordFunc(e, func.name);
572 +
    // Record function code offset for call patching.
573 +
    try emit::recordFuncOffset(e, func.name);
574 +
    // Conditional branches start in their short form. When one does not reach
575 +
    // its target, the body is emitted again with that branch in its long form.
576 +
    let start = emit::beginBody(e);
577 +
    loop {
578 +
        try selectBody(e, ralloc, func, layouts, &frame);
579 +
        // Patch local branches now that all blocks are emitted.
580 +
        if try emit::patchLocalBranches(e) {
581 +
            return;
582 +
        }
583 +
        emit::rewind(e, start);
584 +
    }
585 +
}
586 +
587 +
/// Emit the prologue, the blocks, and the epilogue of a function.
588 +
fn selectBody(
589 +
    e: &mut emit::Emitter,
590 +
    ralloc: regalloc::AllocResult,
591 +
    func: *il::Fn,
592 +
    layouts: &[il::Layout],
593 +
    frame: &emit::Frame
594 +
) throws (super::Error) {
595 +
    // Reset block offsets for this function.
596 +
    labels::resetBlocks(&mut e.labels);
572 597
    // Synthetic block indices start after real blocks and the epilogue block.
573 598
    let mut s = Selector {
574 599
        ralloc,
575 600
        frameSize: frame.totalSize,
576 601
        reserveOffset: 0,
577 602
        pendingSpill: nil,
578 603
        instrIndex: 0,
579 604
        nextSynthBlock: func.blocks.len + 1,
580 605
        argAdjust: 0,
581 606
    };
582 -
    // Record function name for printing.
583 -
    try emit::recordFunc(e, func.name);
584 -
    // Record function code offset for call patching.
585 -
    try emit::recordFuncOffset(e, func.name);
586 607
    // Emit prologue.
587 -
    try emit::emitPrologue(e, &frame);
608 +
    try emit::emitPrologue(e, frame);
588 609
589 610
    // Move function params from arg registers to assigned registers.
590 611
    // Cross-call params may have been assigned to callee-saved registers
591 612
    // instead of their natural arg registers. Spilled params are stored
592 613
    // directly to their spill slots. Params beyond the arg registers are
614 635
            }
615 636
        }
616 637
    }
617 638
    // Emit each block.
618 639
    for i in 0..func.blocks.len {
619 -
        try selectBlock(&mut s, e, i, &func.blocks[i], &frame, func, layouts);
640 +
        try selectBlock(&mut s, e, i, &func.blocks[i], frame, func, layouts);
620 641
    }
621 642
    // Emit epilogue.
622 -
    try emit::emitEpilogue(e, &frame);
623 -
    // Patch local branches now that all blocks are emitted.
624 -
    try emit::patchLocalBranches(e);
643 +
    try emit::emitEpilogue(e, frame);
625 644
}
626 645
627 646
/// Select instructions for a block.
628 647
fn selectBlock(
629 648
    s: &mut Selector,
lib/std/arch/rv64/tests.rad +53 -6
1257 1257
    let tables = try! testLabels(&mut arena);
1258 1258
    let mut e = try! rv64::emit::emitter(arena, false, tables);
1259 1259
    try! rv64::emit::recordBranch(&mut e, 0, rv64::emit::BranchKind::Jump);
1260 1260
    set e.labels.blockOffsets[0] = 0x200000;
1261 1261
    set e.labels.blockCount = 1;
1262 -
    let mut failed = false;
1263 -
    try rv64::emit::patchLocalBranches(&mut e) catch error {
1264 -
        assert error == rv64::Error::Relocation;
1265 -
        set failed = true;
1266 -
    };
1267 -
    assert failed;
1262 +
    assert patchError(&mut e) == rv64::Error::Relocation;
1268 1263
    assert e.code[0] == encode::nop();
1269 1264
}
1270 1265
1266 +
/// Patch the local branches of `e`, returning the error that patching throws.
1267 +
fn patchError(e: &mut rv64::emit::Emitter) -> ?rv64::Error {
1268 +
    let _ = try rv64::emit::patchLocalBranches(e) catch error {
1269 +
        return error;
1270 +
    };
1271 +
    return nil;
1272 +
}
1273 +
1274 +
/// A conditional branch that reaches its target is a single instruction.
1275 +
@test unsafe fn testShortConditionalBranch() throws (testing::TestError) {
1276 +
    let mut arena = alloc::new(&mut ASSEMBLY_ARENA_STORAGE[..]);
1277 +
    let tables = try! testLabels(&mut arena);
1278 +
    let mut e = try! rv64::emit::emitter(arena, false, tables);
1279 +
    let kind = rv64::emit::BranchKind::Cond { op: il::CmpOp::Eq, rs1: rv64::A0, rs2: rv64::A1 };
1280 +
    try! rv64::emit::recordBranch(&mut e, 0, kind);
1281 +
    try! rv64::emit::emit(&mut e, encode::ebreak());
1282 +
    try! rv64::emit::recordBlock(&mut e, 0);
1283 +
    assert try! rv64::emit::patchLocalBranches(&mut e);
1284 +
    assert e.code.len == 2;
1285 +
    assert e.code[0] == encode::beq(rv64::A0, rv64::A1, 8);
1286 +
}
1287 +
1288 +
/// A conditional branch beyond the B-type range makes the function body be
1289 +
/// emitted again, with that branch in its long form. Rewinding keeps what was
1290 +
/// emitted before the body, and the next body starts with short branches.
1291 +
@test unsafe fn testLongConditionalBranch() throws (testing::TestError) {
1292 +
    let mut arena = alloc::new(&mut ASSEMBLY_ARENA_STORAGE[..]);
1293 +
    let tables = try! testLabels(&mut arena);
1294 +
    let mut e = try! rv64::emit::emitter(arena, false, tables);
1295 +
    let kind = rv64::emit::BranchKind::Cond { op: il::CmpOp::Eq, rs1: rv64::A0, rs2: rv64::A1 };
1296 +
    try! rv64::emit::recordCall(&mut e, "before");
1297 +
    let start = rv64::emit::beginBody(&mut e);
1298 +
    try! rv64::emit::recordBranch(&mut e, 0, kind);
1299 +
    try! rv64::emit::recordCall(&mut e, "inside");
1300 +
    set e.labels.blockOffsets[0] = 0x2000;
1301 +
    set e.labels.blockCount = 1;
1302 +
    assert not try! rv64::emit::patchLocalBranches(&mut e);
1303 +
1304 +
    rv64::emit::rewind(&mut e, start);
1305 +
    assert e.code.len == 2;
1306 +
    assert e.pendingCalls.len == 1;
1307 +
    try! rv64::emit::recordBranch(&mut e, 0, kind);
1308 +
    assert e.code.len == 4;
1309 +
    assert try! rv64::emit::patchLocalBranches(&mut e);
1310 +
    assert e.code[2] == encode::bne(rv64::A0, rv64::A1, 8);
1311 +
    assert e.code[3] == encode::jal(rv64::ZERO, 0x2000 - 12);
1312 +
1313 +
    let next = rv64::emit::beginBody(&mut e);
1314 +
    try! rv64::emit::recordBranch(&mut e, 0, kind);
1315 +
    assert e.code.len == next.code + 1;
1316 +
}
1317 +
1271 1318
/// Assembly jumps reject targets beyond the J-type displacement range.
1272 1319
@test unsafe fn testAssemblyJumpRange() throws (testing::TestError) {
1273 1320
    let mut arena = alloc::new(&mut ASSEMBLY_ARENA_STORAGE[..]);
1274 1321
    let tables = try! testLabels(&mut arena);
1275 1322
    let mut e = try! rv64::emit::emitter(arena, false, tables);