radiance · commit

compiler: Publish checked register-allocation inputs

a359ca0dcdc69aec29168ff05130e416d91d903e38d7dae1f109353a7e693e2e

Alexis Sellier committed 5 days ago 1 parent e4713575

lib/std/arch/rv64.rad +2 -1

    generator: &mut Generator,
    func: &il::Fn,
    config: &regalloc::TargetConfig,
    storage: &Session 'scratch
) throws (alloc::AllocError) {
    let ralloc = try regalloc::allocate(func, config, storage);
    let view = try il::published::publish(func, storage);
    let ralloc = try regalloc::allocate(&view, config, storage);
    isel::selectFn(&mut generator.e, &ralloc, func);
}

/// Record an alternate name for the next function emitted.
export fn recordFunctionAlias(generator: &mut Generator, name: *[u8]) {

lib/std/arch/rv64/bounds.rad +2 -1

        let func = il::Fn {
            name: "p::pressure", params: &[], returnType: il::Type::W64, isExtern: false, isLeaf: true,
            blocks: &[il::Block { label: "entry", params: &[], instrs: &mut [], locs: &[], preds: &[], loopDepth: 0 }],
        };
        let mut failed = false;
        try regalloc::spill::analyze(&func, &live, 23, 11, 8, &bits) catch {
        let view = try! il::published::publish(&func, &bits);
        try regalloc::spill::analyze(&view, &live, 23, 11, 8, &bits) catch {
            set failed = true;
        };
        try testing::expect(failed);
    }
}

lib/std/lang/gen/regalloc.rad +3 -3

export mod liveness;
export mod flow;
export mod spill;
export mod assign;

use std::lang::il;
use std::lang::il::published;
use std::lang::alloc;

/// Target configuration for register allocation.
export record TargetConfig: Copy {
    /// List of allocatable physical registers.


/// Run register allocation on a function.
///
/// Returns a mapping from SSA registers to physical registers, plus
/// spill information.
export unsafe fn allocate 'scratch (
    func: &il::Fn,
export fn allocate 'input 'scratch (
    func: &published::Function 'input,
    config: &TargetConfig,
    storage: &Session 'scratch
) -> AllocResult 'scratch throws (alloc::AllocError) {
    // Phase 1: Liveness analysis.
    let live = try liveness::analyze(func, storage);

lib/std/lang/gen/regalloc/assign.rad +13 -20

//!
//! The IL is not modified. Instead, a mapping from SSA registers to physical
//! registers is produced for use by instruction selection.

use std::lang::il;
use std::lang::il::published;
use std::lang::alloc;
use std::lang::gen;
use std::lang::gen::bitset;
use std::lang::gen::regalloc::liveness;
use std::lang::gen::regalloc::spill;

    assignments: &'step mut [?gen::Reg],
    spillInfo: &'step spill::SpillInfo 'scratch,
}

/// Compute register assignment.
export unsafe fn assign 'scratch (
    func: &il::Fn,
export fn assign 'input 'scratch (
    func: &published::Function 'input,
    live: &liveness::LiveInfo 'scratch,
    spillInfo: &spill::SpillInfo 'scratch,
    config: &super::TargetConfig,
    storage: &Session 'scratch
) -> AssignInfo 'scratch throws (alloc::AllocError) {
    return try assignTables(func.params, func.blocks, live, spillInfo, config, storage);
}

/// Allocate register mappings for borrowed function parameter and block tables.
fn assignTables 'scratch (
fn assignTables 'input 'scratch (
    params: &[il::Param],
    blocks: &[il::Block],
    blocks: &[published::Block 'input],
    live: &liveness::LiveInfo 'scratch,
    spillInfo: &spill::SpillInfo 'scratch,
    config: &super::TargetConfig,
    storage: &Session 'scratch,
) -> AssignInfo 'scratch throws (alloc::AllocError) {

                allocatable,
                calleeSaved: config.calleeSaved,
                assignments: assignmentsRef,
                spillInfo: spillRef,
            };
            unsafe {
                assignBlock(block.params, block.instrs, &mut ctx, config);
            }
            assignBlock(block.params, block.instructions, &mut ctx, config);
        }
    }
    // Compute bitmask of used callee-saved registers.
    let mut usedCalleeSaved: u32 = 0;
    for i in 0..maxReg {

        usedCalleeSaved,
    };
}

/// Assign one block's source and destination registers in instruction order.
fn assignBlock 'scratch 'step (
fn assignBlock 'input 'scratch 'step (
    params: &[il::Param],
    instructions: &[il::Instr],
    instructions: &[published::Instruction 'input],
    ctx: &mut InstrCtx 'scratch 'step,
    config: &super::TargetConfig,
) where 'scratch: 'step {
    // Record every operand before allocation. Only current-block operands
    // query this table, so every read is initialized by this scan.
    // Entries for other registers need not be cleared between blocks.
    for i in 0..instructions.len {
        let instr = &instructions[i];
        let mut registers = il::registers(instr);
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                recordLastUse(reg, ctx.lastUse, i);
            }
        for reg in published::registers(instr) {
            recordLastUse(reg, ctx.lastUse, i);
        }
    }

    enterBlock(ctx.current, ctx.usedRegs, liveness::liveInRow(ctx.live, ctx.blockIdx), params, ctx.assignments, config, ctx.spillInfo);

    // Process each instruction.
    for i in 0..instructions.len {
        let instr = &instructions[i];
        set ctx.instrIdx = i;
        let mut registers = il::registers(instr);
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                processInstrReg(reg, ctx);
            }
        for reg in published::registers(instr) {
            processInstrReg(reg, ctx);
        }

        // Allocate destination.
        if let dst = il::instrDst(*instr) {
        if let dst = published::destination(instr) {
            if dst.n < ctx.assignments.len and not spill::isSpilled(ctx.spillInfo, dst) {
                set ctx.assignments[dst.n] = rallocReg(ctx.current, ctx.usedRegs, dst.n, ctx.allocatable, ctx.calleeSaved, ctx.spillInfo);
            }
        }
    }

lib/std/lang/gen/regalloc/flow.rad +11 -30

//! Owned control-flow topology for dataflow analysis.

use std::graph;
use std::lang::alloc;
use std::lang::il;

/// Largest successor count represented by a slice length.
constant MAX_SUCCESSORS: u32 = 0xffffffff;
use std::lang::il::published;

/// Stable block identity and private successor storage.
export opaque record Block: 's + Copy {
    /// Graph capability identity.
    token: graph::Node 's,

    frozen: graph::Frozen 's,
    /// Stable block handles in function order.
    blocks: &'s [Block 's],
}

/// Copy successor topology from valid IL into session-owned storage.
/// Instruction and switch tables must remain valid during this call.
export unsafe fn snapshot 's (blocks: &[il::Block], storage: &Session 's)
/// Copy published successor topology into session-owned graph storage.
export fn snapshot 'input 's (blocks: &[published::Block 'input], storage: &Session 's)
    -> Flow 's throws (alloc::AllocError)
{
    let mut builder = try graph::new(storage);
    let none: [Block 's; 0] = [];
    let empty: &'s [Block 's] = try storage.copy(&none[..]);

    let entries = try storage.fill(first, blocks.len);
    for i in 1..blocks.len {
        set entries[i] = try reserve(&mut builder, i, empty, storage);
    }
    for block, i in blocks {
        let instructions: &[il::Instr] = block.instrs;
        let instructions = block.instructions;
        let mut links = empty;
        if instructions.len > 0 {
            let term = &instructions[instructions.len - 1];
            match term {
                case il::Instr::Jmp { target, .. } => {
                    set links = try storage.fill(entries[*target], 1);
                },
                case il::Instr::Br { thenTarget, elseTarget, .. } => {
                    let targets = try storage.fill(entries[*thenTarget], 2);
                    set targets[1] = entries[*elseTarget];
                    set links = &targets[..];
                },
                case il::Instr::Switch { defaultTarget, cases, .. } => {
                    let cases: &[il::SwitchCase] = *cases;
                    if cases.len == MAX_SUCCESSORS {
                        throw alloc::AllocError::OutOfMemory;
                    }
                    let targets = try storage.fill(entries[*defaultTarget], cases.len + 1);
                    for item, j in cases {
                        set targets[j + 1] = entries[item.target];
                    }
                    set links = &targets[..];
                },
                else => {},
            let targets = published::successors(&instructions[instructions.len - 1]);
            if targets.len > 0 {
                let successors = try storage.fill(entries[targets[0]], targets.len);
                for j in 1..targets.len {
                    set successors[j] = entries[targets[j]];
                }
                set links = &successors[..];
            }
        }
        try! define(&mut builder, entries[i], links);
    }
    return Flow 's { frozen: try! graph::freeze(builder), blocks: &entries[..] };

lib/std/lang/gen/regalloc/liveness.rad +27 -39

//!   }

@test mod tests;

use std::lang::il;
use std::lang::il::published;
use std::lang::alloc;
use std::lang::gen::bitset;
use super::flow;

/// Largest register index whose required entry count fits in u32.

    /// Maximum register number used.
    maxReg: u32,
}

/// Compute liveness by growing live sets until no live-in set changes.
export unsafe fn analyze 'scratch (func: &il::Fn, storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
export fn analyze 'input 'scratch (func: &published::Function 'input, storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
    return try analyzeTables(func.params, func.blocks, storage);
}

/// Allocate and compute live sets for borrowed function parameter and block tables.
fn analyzeTables 'scratch (params: &[il::Param], blocks: &[il::Block], storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
fn analyzeTables 'input 'scratch (params: &[il::Param], blocks: &[published::Block 'input], storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
    let blockCount = blocks.len;
    if blockCount == 0 {
        let empty = try storage.fill(0 as u32, 0);
        let frozen: &'scratch [u32] = &empty[..];
        return LiveInfo 'scratch { liveIn: frozen, liveOut: frozen, defs: frozen, uses: frozen, words: 0, blockCount: 0, maxReg: 0 };
    }

    // Find max register number.
    let mut maxReg: u32 = 0;
    try updateExtent(params, &[], &mut maxReg);
    for parameter in params {
        try updateMaxReg(parameter.value, &mut maxReg);
    }
    for b in 0..blockCount {
        let block = &blocks[b];
        unsafe {
            try updateExtent(block.params, block.instrs, &mut maxReg);
        }
        try updateExtent(block.params, block.instructions, &mut maxReg);
    }
    // Allocate one contiguous word matrix for each set class.
    let words = bitset::wordsFor(maxReg);
    let count64 = blockCount as u64 * words as u64;
    if count64 > 0xFFFFFFFF {

    let uses = try storage.fill(0 as u32, count);

    // Compute local defs and uses for each block.
    for b in 0..blockCount {
        let block = &blocks[b];
        unsafe {
            computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
        }
    }
    unsafe {
        let topology = try flow::snapshot(blocks, storage);
        propagateLiveness(&topology, blockCount, liveIn, liveOut, defs, uses, words);
        computeLocalDefsUses(block.params, block.instructions, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
    }
    let topology = try flow::snapshot(blocks, storage);
    propagateLiveness(&topology, blockCount, liveIn, liveOut, defs, uses, words);
    return LiveInfo 'scratch { liveIn: &liveIn[..], liveOut: &liveOut[..], defs: &defs[..], uses: &uses[..], words, blockCount, maxReg };
}

/// Propagate successor uses until every block's live-in row is stable.
fn propagateLiveness 'scratch (

    }
    return changed;
}

/// Compute local defs and uses for a single block.
fn computeLocalDefsUses(params: &[il::Param], instructions: &[il::Instr], defs: &mut [u32], uses: &mut [u32]) {
fn computeLocalDefsUses 'input (params: &[il::Param], instructions: &[published::Instruction 'input], defs: &mut [u32], uses: &mut [u32]) {
    for p in params {
        bitset::put(defs, p.value.n);
    }
    for i in 0..instructions.len {
        let instr = &instructions[i];
        let mut registers = il::registers(instr);
        // Argument groups contain raw views into the function's IL storage.
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                addUse(reg, defs, uses);
            }
        // Fixed operands precede the instruction's variable argument groups.
        for reg in published::registers(instr) {
            addUse(reg, defs, uses);
        }

        if let dst = il::instrDst(*instr) {
        if let dst = published::destination(instr) {
            bitset::put(defs, dst.n);
        }
    }
}


        bitset::put(uses, reg.n);
    }
}

/// Include all parameter, source, and destination registers in the entry count.
fn updateExtent(params: &[il::Param], instructions: &[il::Instr], max: &mut u32) throws (alloc::AllocError) {
fn updateExtent 'input (params: &[il::Param], instructions: &[published::Instruction 'input], max: &mut u32) throws (alloc::AllocError) {
    for p in params {
        try updateMaxReg(p.value, max);
    }
    for i in 0..instructions.len {
        let instr = &instructions[i];
        let mut registers = il::registers(instr);
        // Argument groups contain raw views into the function's IL storage.
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                try updateMaxReg(reg, max);
            }
        // Fixed operands precede the instruction's variable argument groups.
        for reg in published::registers(instr) {
            try updateMaxReg(reg, max);
        }
        if let dst = il::instrDst(*instr) {
        if let dst = published::destination(instr) {
            try updateMaxReg(dst, max);
        }
    }
}


fn unionBlockLiveIn(target: u32, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
    bitset::union_(liveOut, &liveIn[target * words..(target + 1) * words]);
}

/// Check if a register has any use after this instruction.
export unsafe fn hasLaterUse 'scratch (info: &LiveInfo 'scratch, func: &il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
export fn hasLaterUse 'input 'scratch (info: &LiveInfo 'scratch, func: &published::Function 'input, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
    let block = &func.blocks[blockIdx];

    if bitset::contains(liveOutRow(info, blockIdx), reg.n) {
        return true;
    }
    return usesRegisterAfter(block.instrs, instrIdx, reg);
    return usesRegisterAfter(block.instructions, instrIdx, reg);
}

/// Check if an instruction after the given index uses a specific register.
fn usesRegisterAfter(instructions: &[il::Instr], instrIdx: u32, reg: il::Reg) -> bool {
fn usesRegisterAfter 'input (instructions: &[published::Instruction 'input], instrIdx: u32, reg: il::Reg) -> bool {
    for i in (instrIdx + 1)..instructions.len {
        let instr = &instructions[i];
        let mut registers = il::registers(instr);
        // Argument groups contain raw views into the function's IL storage.
        unsafe {
            while let source = il::nextReg(&mut registers, instr) {
                if source.n == reg.n {
                    return true;
                }
        // Fixed operands precede the instruction's variable argument groups.
        for source in published::registers(instr) {
            if source.n == reg.n {
                return true;
            }
        }
    }
    return false;
}

lib/std/lang/gen/regalloc/liveness/tests.rad +84 -30

//! Tests for liveness analysis.

use std::testing;
use std::lang::alloc;
use std::lang::il;
use std::lang::il::published;
use std::lang::gen::bitset;
use std::lang::gen::regalloc::spill;
use std::lang::gen::regalloc::assign;
use std::lang::gen::regalloc;
use std::lang::gen::regalloc::flow;

/// Publish fixture inputs outside the arena whose analysis capacity is tested.
unsafe fn analyze 'scratch (function: &il::Fn, storage: &Session 'scratch)
    -> super::LiveInfo 'scratch throws (alloc::AllocError)
{
    static DATA: [u8; 65536] = [0; 65536];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as inputs in {
        let view = try published::publish(function, &inputs);
        return try super::analyze(&view, storage);
    }
}

/// Publish fixture inputs outside the arena whose spill capacity is tested.
unsafe fn analyzeSpills 'scratch (function: &il::Fn, live: &super::LiveInfo 'scratch,
    numRegs: u32, numCalleeSaved: u32, slotSize: u32, storage: &Session 'scratch)
    -> spill::SpillInfo 'scratch throws (alloc::AllocError)
{
    static DATA: [u8; 65536] = [0; 65536];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as inputs in {
        let view = try published::publish(function, &inputs);
        return try spill::analyze(&view, live, numRegs, numCalleeSaved, slotSize, storage);
    }
}

/// Publish fixture inputs outside the arena whose assignment capacity is tested.
unsafe fn assignRegisters 'scratch (function: &il::Fn, live: &super::LiveInfo 'scratch,
    spills: &spill::SpillInfo 'scratch, config: &regalloc::TargetConfig, storage: &Session 'scratch)
    -> assign::AssignInfo 'scratch throws (alloc::AllocError)
{
    static DATA: [u8; 65536] = [0; 65536];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as inputs in {
        let view = try published::publish(function, &inputs);
        return try assign::assign(&view, live, spills, config, storage);
    }
}

/// Publish CFG fixture inputs outside the graph allocation test arena.
unsafe fn snapshot 'scratch (blocks: &[il::Block], storage: &Session 'scratch)
    -> flow::Flow 'scratch throws (alloc::AllocError)
{
    let function = il::Fn { name: "topology", params: &[], returnType: il::Type::W64,
        isExtern: false, isLeaf: true, blocks: blocks as *unsafe [il::Block] };
    static DATA: [u8; 4096] = [0; 4096];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as inputs in {
        let view = try published::publish(&function, &inputs);
        return try flow::snapshot(view.blocks, storage);
    }
}

/// Frozen topology owns successor tables and preserves cyclic block identities.
@test unsafe fn testOwnedFlowSnapshot() throws (testing::TestError) {
    let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut [] }];
    let mut first = [il::Instr::Switch { val: il::Val::Imm(0), defaultTarget: 0,
        defaultArgs: &mut [], cases: &mut cases[..] }];
    let mut second = [il::Instr::Jmp { target: 0, args: &mut [] }];
    let blocks = [block("first", &mut first[..]), block("second", &mut second[..])];
    static DATA: [u8; 2048] = [0; 2048];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as storage in {
        let frozen = try! flow::snapshot(&blocks[..], &storage);
        let frozen = try! snapshot(&blocks[..], &storage);
        set cases[0].target = 0;
        set first[0] = il::Instr::Ret { val: il::Val::Imm(0) };
        set second[0] = il::Instr::Ret { val: il::Val::Imm(0) };
        let successors = flow::successors(&frozen, 0);
        assert successors.len == 2;

    let mut succeeded = false;
    for capacity in 0..257 {
        static DATA: [u8; 256] = [0; 256];
        let mut arena = alloc::new(&mut DATA[..capacity]);
        use arena as storage in {
            if let frozen = try? flow::snapshot(&blocks[..], &storage) {
            if let frozen = try? snapshot(&blocks[..], &storage) {
                let links = flow::successors(&frozen, 0);
                assert links.len == 1 and flow::index(links[0]) == 0;
                set succeeded = true;
            } else {
                assert not succeeded;

        let function = il::Fn { name: "empty", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..count] };
        static DATA: [u8; 1024] = [0; 1024];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let live = try! analyze(&function, &analysis);
            assert live.blockCount == count;
            assert live.maxReg == 0;
            assert live.words == 0;
            assert live.liveIn.len == 0 and live.liveOut.len == 0;
            assert live.defs.len == 0 and live.uses.len == 0;
            let spills = try! spill::analyze(&function, &live, 0, 0, 8, &analysis);
            let spills = try! analyzeSpills(&function, &live, 0, 0, 8, &analysis);
            assert spills.maxReg == 0;
            assert spills.frameSize == 0;
            assert spills.slots.len == 0 and spills.calleeClass.len == 0;
            let config = regalloc::TargetConfig { allocatable: &[], argRegs: &[], calleeSaved: &[], slotSize: 8 };
            let assigned = try! assign::assign(&function, &live, &spills, &config, &analysis);
            let assigned = try! assignRegisters(&function, &live, &spills, &config, &analysis);
            assert assigned.assignments.len == 0;
            assert assigned.usedCalleeSaved == 0;
        }
    }
}

        isExtern: false, isLeaf: true, blocks: &blocks[..] };
    static DATA: [u8; 16] = [0; 16];
    let mut arena = alloc::new(&mut DATA[..]);
    let mut failed = false;
    use arena as analysis in {
        try super::analyze(&function, &analysis) catch {
        try analyze(&function, &analysis) catch {
            set failed = true;
        };
    }
    assert failed;
}

        isExtern: false, isLeaf: true, blocks: &blocks[..] };
    static DATA: [u8; 128] = [0; 128];
    let mut arena = alloc::new(&mut DATA[..]);
    let mut failed = false;
    use arena as analysis in {
        let live = try! super::analyze(&function, &analysis);
        try spill::analyze(&function, &live, 0, 0, 8, &analysis) catch {
        let live = try! analyze(&function, &analysis);
        try analyzeSpills(&function, &live, 0, 0, 8, &analysis) catch {
            set failed = true;
        };
    }
    assert failed;
}

        let function = il::Fn { name: "switch", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 8192] = [0; 8192];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let live = try! analyze(&function, &analysis);
            try check(super::liveOutRow(&live, 0), count > 0, count == 3, true);
            try check(super::liveInRow(&live, 0), count > 0, count == 3, true);
            try check(super::liveOutRow(&live, 4), false, false, false);
        }
    }

    let function = il::Fn { name: "cycle", params: &[], returnType: il::Type::W64,
        isExtern: false, isLeaf: true, blocks: &blocks[..] };
    static DATA: [u8; 8192] = [0; 8192];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as analysis in {
        let live = try! super::analyze(&function, &analysis);
        let live = try! analyze(&function, &analysis);
        for index in 0..blocks.len {
            try check(super::liveInRow(&live, index), false, false, index > 0 and index < 4);
            try check(super::liveOutRow(&live, index), false, false, index <> 1 and index < 4);
        }
    }

    let function = il::Fn { name: "later", params: &params[..], returnType: il::Type::W64,
        isExtern: false, isLeaf: false, blocks: &blocks[..] };
    static DATA: [u8; 8192] = [0; 8192];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as analysis in {
        let live = try! super::analyze(&function, &analysis);
        let live = try! analyze(&function, &analysis);
        let view = try! published::publish(&function, &analysis);
        for index in 0..entry.len {
            assert super::hasLaterUse(&live, &function, 0, index, outgoing);
            assert super::hasLaterUse(&live, &function, 0, index, argument) == (index == 0);
            assert super::hasLaterUse(&live, &function, 0, index, result) == (index < 2);
            assert not super::hasLaterUse(&live, &function, 0, index, unused);
            assert super::hasLaterUse(&live, &view, 0, index, outgoing);
            assert super::hasLaterUse(&live, &view, 0, index, argument) == (index == 0);
            assert super::hasLaterUse(&live, &view, 0, index, result) == (index < 2);
            assert not super::hasLaterUse(&live, &view, 0, index, unused);
        }
        assert not super::hasLaterUse(&live, &function, 1, 0, outgoing);
        assert not super::hasLaterUse(&live, &view, 1, 0, outgoing);
    }
}

/// Local uses precede definitions, and block parameters define their registers.
@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {

    let function = il::Fn { name: "local", params: &[], returnType: il::Type::W64,
        isExtern: false, isLeaf: true, blocks: &blocks[..] };
    static DATA: [u8; 8192] = [0; 8192];
    let mut arena = alloc::new(&mut DATA[..]);
    use arena as analysis in {
        let live = try! super::analyze(&function, &analysis);
        let live = try! analyze(&function, &analysis);
        try check(&live.defs[..live.words], true, true, true);
        try check(&live.uses[..live.words], true, false, false);
        try check(super::liveInRow(&live, 0), true, false, false);
        try check(&live.defs[live.words..], false, false, false);
        try check(&live.uses[live.words..], false, false, false);

        let function = il::Fn { name: "extent", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 16384] = [0; 16384];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try super::analyze(&function, &analysis) catch {
            let live = try analyze(&function, &analysis) catch {
                throw testing::TestError::Failed;
            };
            assert live.maxReg == index + 2;
            assert bitset::contains(super::liveInRow(&live, 0), source.n);
            assert bitset::contains(&live.defs[..], destination.n);

            let function = il::Fn { name: "argument", params: &[], returnType: il::Type::W64,
                isExtern: false, isLeaf: true, blocks: &blocks[..] };
            static DATA: [u8; 32768] = [0; 32768];
            let mut arena = alloc::new(&mut DATA[..]);
            use arena as analysis in {
                let live = try super::analyze(&function, &analysis) catch {
                let live = try analyze(&function, &analysis) catch {
                    assert index == 0xffffffff;
                    continue;
                };
                assert index <> 0xffffffff;
                assert live.maxReg == index + 1;

            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 1024] = [0; 1024];
        let mut arena = alloc::new(&mut DATA[..]);
        let mut failed = false;
        use arena as analysis in {
            try super::analyze(&function, &analysis) catch {
            try analyze(&function, &analysis) catch {
                set failed = true;
            };
        }
        assert failed;
        assert arena.offset == 0;

        let function = il::Fn { name: "offsets", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 16384] = [0; 16384];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {
            let live = try! analyze(&function, &analysis);
            let info = try analyzeSpills(&function, &live, 0, 0, size, &analysis) catch {
                assert size == 0x2aaaaaab;
                continue;
            };
            assert size <= 0x2aaaaaaa;
            assert info.slots[0] == 0;

        let function = il::Fn { name: "frame", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 4096] = [0; 4096];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {
            let live = try! analyze(&function, &analysis);
            let info = try analyzeSpills(&function, &live, 0, 0, size, &analysis) catch {
                assert size > 0x7fffffff;
                continue;
            };
            assert size == 0x7fffffff;
            assert info.frameSize == 2147483647;

        let function = il::Fn { name: "weighted", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 8192] = [0; 8192];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let info = try! spill::analyze(&function, &live, 1, 0, 8, &analysis);
            let live = try! analyze(&function, &analysis);
            let info = try! analyzeSpills(&function, &live, 1, 0, 8, &analysis);
            assert spill::isSpilled(&info, first) == (depth == 0);
            assert spill::isSpilled(&info, second) == (depth > 0);
            assert not spill::isSpilled(&info, temporary);
            assert info.frameSize == 8;
        }

        isExtern: false, isLeaf: false, blocks: &blocks[..] };
    for capacity in [0 as u32, 1, 2] {
        static DATA: [u8; 8192] = [0; 8192];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let info = try! spill::analyze(&function, &live, 8, capacity, 8, &analysis);
            let live = try! analyze(&function, &analysis);
            let info = try! analyzeSpills(&function, &live, 8, capacity, 8, &analysis);
            assert spill::isSpilled(&info, first) == (capacity < 2);
            assert spill::isSpilled(&info, second) == (capacity == 0);
            assert not spill::isSpilled(&info, result);
            assert not spill::isSpilled(&info, sum);
            assert not spill::isSpilled(&info, total);

                set function.params = &parameters[..];
            }
            static DATA: [u8; 16384] = [0; 16384];
            let mut arena = alloc::new(&mut DATA[..]);
            use arena as analysis in {
                let live = try super::analyze(&function, &analysis) catch {
                let live = try analyze(&function, &analysis) catch {
                    assert index == 0xffffffff;
                    continue;
                };
                assert index == 16384;
                assert live.maxReg == index + 1;

        isExtern: false, isLeaf: true, blocks: &blocks[..] };
    static DATA: [u8; 8192] = [0; 8192];
    let mut arena = alloc::new(&mut DATA[..]);
    let mut answer: u32 = 0;
    use arena as analysis in {
        let live = try! super::analyze(&function, &analysis);
        let live = try! analyze(&function, &analysis);
        try testing::expect(live.blockCount == 4);
        try testing::expect(live.maxReg == 67);
        try testing::expect(live.words == 3);
        try check(super::liveInRow(&live, 0), false, false, false);
        try check(super::liveOutRow(&live, 0), true, false, false);

lib/std/lang/gen/regalloc/spill.rad +20 -29

//!
//! * Spill slot assignments: SSA reg -> stack offset, `-1` if not spilled.
//! * Total frame size needed for spills.

use std::lang::il;
use std::lang::il::published;
use std::lang::alloc;
use std::lang::gen::bitset;
use std::lang::gen::regalloc::liveness;

/// Maximum number of candidates for spill sorting.

    reg: u32,
    cost: u32,
}

/// Analyze a function and determine which values need spill slots.
export unsafe fn analyze 'scratch (
    func: &il::Fn,
export fn analyze 'input 'scratch (
    func: &published::Function 'input,
    live: &liveness::LiveInfo 'scratch,
    numRegs: u32,
    numCalleeSaved: u32,
    slotSize: u32,
    storage: &Session 'scratch
) -> SpillInfo 'scratch throws (alloc::AllocError) {
    return try analyzeBlocks(func.blocks, live, numRegs, numCalleeSaved, slotSize, storage);
}

/// Allocate spill storage and analyze pressure over a borrowed block table.
fn analyzeBlocks 'scratch (
    blocks: &[il::Block],
fn analyzeBlocks 'input 'scratch (
    blocks: &[published::Block 'input],
    live: &liveness::LiveInfo 'scratch,
    numRegs: u32,
    numCalleeSaved: u32,
    slotSize: u32,
    storage: &Session 'scratch,

    // Allocate cost array.
    let costs = try storage.fill(SpillCost { defs: 0, uses: 0 }, maxReg);
    // Phase 1: Calculate spill costs.
    for b in 0..blocks.len {
        let block = &blocks[b];
        unsafe {
            fillCosts(block.params, block.instrs, block.loopDepth, costs);
        }
        fillCosts(block.params, block.instructions, block.loopDepth, costs);
    }

    // Phase 2: Find values that exceed register pressure.
    let spilled = try bitset::allocate(storage, maxReg);
    let calleeClass = try bitset::allocate(storage, maxReg);

        let block = &blocks[b];

        // Start with live-out set.
        bitset::copy(scratch, liveness::liveOutRow(live, b));

        unsafe {
            try limitBlockPressure(block.instrs, scratch, spilled, costs, calleeClass, numRegs, numCalleeSaved);
        }
        try limitBlockPressure(block.instructions, scratch, spilled, costs, calleeClass, numRegs, numCalleeSaved);
    }

    let frameSize = try finishSpills(slots, spilled, calleeClass, numCalleeSaved, slotSize);
    return SpillInfo 'scratch { slots: &slots[..], frameSize, calleeClass: &calleeClass[..], maxReg };
}

/// Limit register pressure from the block's live-out set to its entry.
fn limitBlockPressure(
    instructions: &[il::Instr],
fn limitBlockPressure 'input (
    instructions: &[published::Instruction 'input],
    live: &mut [u32],
    spilled: &mut [u32],
    costs: &[SpillCost],
    calleeClass: &mut [u32],
    numRegs: u32,


        // Limit register pressure before processing this instruction.
        try limitPressure(live, spilled, costs, numRegs);

        // Enforce cross-call pressure at call sites.
        if il::isCall(*instr) {
        if published::isCall(instr) {
            try limitCrossCallPressure(
                live, spilled, costs,
                calleeClass, numCalleeSaved, il::instrDst(*instr)
                calleeClass, numCalleeSaved, published::destination(instr)
            );
        }
        // Remove definition from live set.
        if let dst = il::instrDst(*instr) {
        if let dst = published::destination(instr) {
            bitset::clear(live, dst.n);
        }
        // Add uses to live set.
        let mut registers = il::registers(instr);
        // Argument groups contain raw views into the function's IL storage.
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                bitset::put(live, reg.n);
            }
        // Fixed operands precede the instruction's variable argument groups.
        for reg in published::registers(instr) {
            bitset::put(live, reg.n);
        }
    }
    // Also limit pressure at block entry.
    try limitPressure(live, spilled, costs, numRegs);
}

    }
    return frameSize;
}

/// Add one block's register spill costs, weighted by loop depth.
fn fillCosts(params: &[il::Param], instructions: &[il::Instr], loopDepth: u32, costs: &mut [SpillCost]) {
fn fillCosts 'input (params: &[il::Param], instructions: &[published::Instruction 'input], loopDepth: u32, costs: &mut [SpillCost]) {
    // Exponential weight for loop depth, capped to avoid overflow.
    let depth = MAX_LOOP_WEIGHT if loopDepth > MAX_LOOP_WEIGHT else loopDepth;
    let weight: u32 = 1 << depth;

    // Count block parameter definitions.

    // Count instruction defs and uses.
    for i in 0..instructions.len {
        let instr = &instructions[i];

        // Count definition.
        if let dst = il::instrDst(*instr) {
        if let dst = published::destination(instr) {
            if dst.n < costs.len {
                set costs[dst.n].defs = costs[dst.n].defs + weight;
            }
        }
        // Count uses.
        let mut registers = il::registers(instr);
        // Argument groups contain raw views into the function's IL storage.
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                countRegUse(reg, &mut costs[..], weight);
            }
        // Fixed operands precede the instruction's variable argument groups.
        for reg in published::registers(instr) {
            countRegUse(reg, &mut costs[..], weight);
        }
    }
}

/// Sort candidates by cost (ascending) using insertion sort, then spill

lib/std/lang/il.rad +2 -0


// TODO: Labels should have their own type.
// TODO: Blocks should have an instruction in `Instr`.

export mod printer;
export mod published;
@test mod publishedTests;
export mod binary;
@test mod tests;

use std::lang::alloc;


lib/std/lang/il/published.rad added +157 -0

1	+	//! Immutable, region-bound views of IL used by function analyses.
2	+	//!
3	+	//! Publication owns analysis tables and retains original node pointers as
4	+	//! identities. Analysis reads do not access the source tables.
5	+
6	+	use std::lang::alloc;
7	+	use std::lang::il;
8	+
9	+	/// Largest element count represented by an analysis slice.
10	+	constant MAX_ELEMENTS: u32 = 0xffffffff;
11	+
12	+	/// Published function tables within one analysis lifetime.
13	+	export record Function: 'view + Copy {
14	+	/// Function parameter definitions.
15	+	params: &'view [il::Param],
16	+	/// Blocks in source order.
17	+	blocks: &'view [Block 'view],
18	+	}
19	+
20	+	/// Read-only block tables and their original identity.
21	+	export record Block: 'view + Copy {
22	+	/// Original block pointer, used only for identity comparisons.
23	+	identity: *unsafe il::Block,
24	+	/// Block parameter definitions.
25	+	params: &'view [il::Param],
26	+	/// Published instruction descriptors.
27	+	instructions: &'view [Instruction 'view],
28	+	/// Loop nesting depth for cost weighting.
29	+	loopDepth: u32,
30	+	}
31	+
32	+	/// An instruction's immutable register-allocation inputs.
33	+	export opaque record Instruction: 'view + Copy {
34	+	/// Original instruction pointer, used only for identity comparisons.
35	+	identity: *unsafe il::Instr,
36	+	/// Destination register, when the instruction defines a value.
37	+	destination: ?il::Reg,
38	+	/// Whether the instruction has call-clobber semantics.
39	+	isCall: bool,
40	+	/// Source registers in operand order, including repeated uses.
41	+	operands: &'view [il::Reg],
42	+	/// Successor block positions in branch order.
43	+	targets: &'view [u32],
44	+	}
45	+
46	+	/// Copy analysis tables from valid IL into session-owned immutable storage.
47	+	/// All source tables and nested arrays must remain valid during this call.
48	+	/// Original node pointers are identity values, not published storage borrows.
49	+	export unsafe fn publish 'view (function: &il::Fn, storage: &Session 'view)
50	+	-> Function 'view throws (alloc::AllocError)
51	+	{
52	+	let params = try storage.copy(function.params);
53	+	let blocks: &[il::Block] = function.blocks;
54	+	if blocks.len == 0 {
55	+	let none: [Block 'view; 0] = [];
56	+	return Function 'view { params, blocks: try storage.copy(&none[..]) };
57	+	}
58	+	let first = try publishBlock(&blocks[0], storage);
59	+	let views = try storage.fill(first, blocks.len);
60	+	for i in 1..blocks.len {
61	+	set views[i] = try publishBlock(&blocks[i], storage);
62	+	}
63	+	return Function 'view { params, blocks: &views[..] };
64	+	}
65	+
66	+	/// Copy block definitions and each instruction's analysis tables.
67	+	unsafe fn publishBlock 'view (block: &il::Block, storage: &Session 'view)
68	+	-> Block 'view throws (alloc::AllocError)
69	+	{
70	+	let params = try storage.copy(block.params);
71	+	let instructions: &[il::Instr] = block.instrs;
72	+	if instructions.len == 0 {
73	+	let none: [Instruction 'view; 0] = [];
74	+	return Block 'view { identity: block as *unsafe il::Block, params,
75	+	instructions: try storage.copy(&none[..]), loopDepth: block.loopDepth };
76	+	}
77	+	let first = try publishInstruction(&instructions[0], storage);
78	+	let views = try storage.fill(first, instructions.len);
79	+	for i in 1..instructions.len {
80	+	set views[i] = try publishInstruction(&instructions[i], storage);
81	+	}
82	+	return Block 'view { identity: block as *unsafe il::Block, params,
83	+	instructions: &views[..], loopDepth: block.loopDepth };
84	+	}
85	+
86	+	/// Collect source registers and successor positions for one instruction.
87	+	unsafe fn publishInstruction 'view (source: &il::Instr, storage: &Session 'view)
88	+	-> Instruction 'view throws (alloc::AllocError)
89	+	{
90	+	let noTargets: [u32; 0] = [];
91	+	let mut targets: &'view [u32] = try storage.copy(&noTargets[..]);
92	+	match source {
93	+	case il::Instr::Jmp { target, .. } => {
94	+	set targets = try storage.fill(*target, 1);
95	+	},
96	+	case il::Instr::Br { thenTarget, elseTarget, .. } => {
97	+	let edges = try storage.fill(*thenTarget, 2);
98	+	set edges[1] = *elseTarget;
99	+	set targets = &edges[..];
100	+	},
101	+	case il::Instr::Switch { defaultTarget, cases, .. } => {
102	+	let cases: &[il::SwitchCase] = *cases;
103	+	if cases.len == MAX_ELEMENTS {
104	+	throw alloc::AllocError::OutOfMemory;
105	+	}
106	+	let edges = try storage.fill(*defaultTarget, cases.len + 1);
107	+	for item, i in cases {
108	+	set edges[i + 1] = item.target;
109	+	}
110	+	set targets = &edges[..];
111	+	},
112	+	else => {},
113	+	}
114	+	let mut cursor = il::registers(source);
115	+	let mut count: u32 = 0;
116	+	while let reg = il::nextReg(&mut cursor, source) {
117	+	if count == MAX_ELEMENTS {
118	+	throw alloc::AllocError::OutOfMemory;
119	+	}
120	+	set count += 1;
121	+	}
122	+	let operands = try storage.fill(il::Reg { n: 0 }, count);
123	+	set cursor = il::registers(source);
124	+	for i in 0..count {
125	+	let reg = il::nextReg(&mut cursor, source)
126	+	else panic "publishInstruction: operand count changed";
127	+	set operands[i] = reg;
128	+	}
129	+	return Instruction 'view { identity: source as *unsafe il::Instr,
130	+	destination: il::instrDst(source), isCall: il::isCall(source),
131	+	operands: &operands[..], targets };
132	+	}
133	+
134	+	/// Return the original instruction pointer for identity comparisons.
135	+	export fn identity 'view (instruction: &Instruction 'view) -> *unsafe il::Instr {
136	+	return instruction.identity;
137	+	}
138	+
139	+	/// Return an instruction's destination register.
140	+	export fn destination 'view (instruction: &Instruction 'view) -> ?il::Reg {
141	+	return instruction.destination;
142	+	}
143	+
144	+	/// Check whether an instruction has call-clobber semantics.
145	+	export fn isCall 'view (instruction: &Instruction 'view) -> bool {
146	+	return instruction.isCall;
147	+	}
148	+
149	+	/// Borrow successor positions in branch order, including repeated targets.
150	+	export fn successors 'view (instruction: &Instruction 'view) -> &'view [u32] {
151	+	return instruction.targets;
152	+	}
153	+
154	+	/// Borrow source registers in operand order, including repeated uses.
155	+	export fn registers 'view (instruction: &Instruction 'view) -> &'view [il::Reg] {
156	+	return instruction.operands;
157	+	}

lib/std/lang/il/publishedTests.rad added +123 -0

1	+	//! Checked traversal of published IL operand tables.
2	+
3	+	use std::testing;
4	+	use std::lang::alloc;
5	+	use std::lang::il;
6	+	use std::lang::il::published;
7	+
8	+	/// Publish operands from source tables that end with this stack frame.
9	+	unsafe fn transientInput 'view (storage: &Session 'view) -> published::Function 'view
10	+	throws (alloc::AllocError)
11	+	{
12	+	let params = [il::Param { value: il::Reg { n: 5 }, type: il::Type::W64 }];
13	+	let blockParams = [il::Param { value: il::Reg { n: 6 }, type: il::Type::W64 }];
14	+	let mut instructions = [
15	+	il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: il::Reg { n: 9 },
16	+	a: il::Val::Reg(il::Reg { n: 5 }), b: il::Val::Reg(il::Reg { n: 6 }) },
17	+	il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 9 }) },
18	+	];
19	+	let blocks = [il::Block { label: "entry", params: &blockParams[..], instrs: &mut instructions[..],
20	+	locs: &[], preds: &[], loopDepth: 2 }];
21	+	let function = il::Fn { name: "transient", params: &params[..], returnType: il::Type::W64,
22	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
23	+	return try published::publish(&function, storage);
24	+	}
25	+
26	+	/// Analysis tables remain valid after their source stack frame returns.
27	+	@test unsafe fn testTransientPublishedInput() throws (testing::TestError) {
28	+	static DATA: [u8; 4096] = [0; 4096];
29	+	let mut arena = alloc::new(&mut DATA[..]);
30	+	use arena as storage in {
31	+	let view = try! transientInput(&storage);
32	+	assert view.params.len == 1 and view.params[0].value.n == 5;
33	+	let block = &view.blocks[0];
34	+	assert block.params.len == 1 and block.params[0].value.n == 6;
35	+	assert block.loopDepth == 2;
36	+	let registers = published::registers(&block.instructions[0]);
37	+	assert registers.len == 2 and registers[0].n == 5 and registers[1].n == 6;
38	+	let destination = published::destination(&block.instructions[0]) else panic;
39	+	assert destination.n == 9;
40	+	assert not published::isCall(&block.instructions[0]);
41	+	let returned = published::registers(&block.instructions[1]);
42	+	assert returned.len == 1 and returned[0].n == 9;
43	+	assert published::destination(&block.instructions[1]) == nil;
44	+	assert published::successors(&block.instructions[1]).len == 0;
45	+	}
46	+	}
47	+
48	+	/// Empty functions require no analysis storage.
49	+	@test unsafe fn testEmptyPublication() throws (testing::TestError) {
50	+	let function = il::Fn { name: "empty", params: &[], returnType: il::Type::W64,
51	+	isExtern: true, isLeaf: true, blocks: &[] };
52	+	static DATA: [u8; 1] = [0; 1];
53	+	let mut arena = alloc::new(&mut DATA[..0]);
54	+	use arena as storage in {
55	+	let view = try! published::publish(&function, &storage);
56	+	assert view.params.len == 0 and view.blocks.len == 0;
57	+	}
58	+	assert alloc::used(&arena) == 0;
59	+	}
60	+
61	+	/// Publication retains source identities and scans nested argument groups.
62	+	@test unsafe fn testPublishedOperands() throws (testing::TestError) {
63	+	let value = il::Val::Reg(il::Reg { n: 7 });
64	+	let mut arguments = [il::Val::Imm(3), value, value];
65	+	let mut cases = [il::SwitchCase { value: 1, target: 0, args: &mut arguments[..] }];
66	+	let mut instructions = [il::Instr::Switch { val: value, defaultTarget: 0,
67	+	defaultArgs: &mut [], cases: &mut cases[..] }];
68	+	let blocks = [il::Block { label: "entry", params: &[], instrs: &mut instructions[..],
69	+	locs: &[], preds: &[], loopDepth: 0 }];
70	+	let function = il::Fn { name: "published", params: &[], returnType: il::Type::W64,
71	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
72	+	static DATA: [u8; 4096] = [0; 4096];
73	+	let mut arena = alloc::new(&mut DATA[..]);
74	+	let input: 'input = &function in {
75	+	use arena as storage in {
76	+	let view = try! published::publish(input, &storage);
77	+	assert view.blocks.len == 1;
78	+	assert view.blocks[0].identity == &blocks[0];
79	+	let instruction = &view.blocks[0].instructions[0];
80	+	assert published::identity(instruction) == &instructions[0];
81	+	set arguments[1] = il::Val::Reg(il::Reg { n: 99 });
82	+	set cases[0].target = 42;
83	+	set instructions[0] = il::Instr::Ret { val: nil };
84	+	let registers = published::registers(instruction);
85	+	assert registers.len == 3;
86	+	for reg in registers {
87	+	assert reg.n == 7;
88	+	}
89	+	let targets = published::successors(instruction);
90	+	assert targets.len == 2 and targets[0] == 0 and targets[1] == 0;
91	+	}
92	+	}
93	+	}
94	+
95	+	/// Allocation failures leave no borrowed source storage in published results.
96	+	@test unsafe fn testPublicationAllocationFailure() throws (testing::TestError) {
97	+	let args = [il::Val::Reg(il::Reg { n: 4 })];
98	+	let mut instructions = [il::Instr::Call { retTy: il::Type::W64, dst: nil,
99	+	func: il::Val::FnAddr("callee"), args: &args[..] }];
100	+	let blocks = [il::Block { label: "entry", params: &[], instrs: &mut instructions[..],
101	+	locs: &[], preds: &[], loopDepth: 0 }];
102	+	let function = il::Fn { name: "allocation", params: &[], returnType: il::Type::W64,
103	+	isExtern: false, isLeaf: false, blocks: &blocks[..] };
104	+	let mut succeeded = false;
105	+	for capacity in 0..513 {
106	+	static DATA: [u8; 512] = [0; 512];
107	+	let mut arena = alloc::new(&mut DATA[..capacity]);
108	+	let input: 'input = &function in {
109	+	use arena as storage in {
110	+	if let view = try? published::publish(input, &storage) {
111	+	let registers = published::registers(&view.blocks[0].instructions[0]);
112	+	assert registers.len == 1 and registers[0].n == 4;
113	+	set succeeded = true;
114	+	} else {
115	+	assert not succeeded;
116	+	}
117	+	}
118	+	}
119	+	alloc::reset(&mut arena);
120	+	assert alloc::used(&arena) == 0;
121	+	}
122	+	assert succeeded;
123	+	}

std.lib +1 -0

lib/std/lang/ast.rad
lib/std/lang/ast/printer.rad
lib/std/lang/scanner.rad
lib/std/lang/parser.rad
lib/std/lang/il.rad
lib/std/lang/il/published.rad
lib/std/lang/il/printer.rad
lib/std/lang/il/binary.rad
lib/std/lang/il/binary/writer.rad
lib/std/lang/il/binary/reader.rad
lib/std/lang/il/binary/program.rad

std.lib.test +1 -0

lib/std/arch/rv64/shared/tests.rad
lib/std/arch/rv64/bounds.rad
lib/std/arch/rv64/atomicTests.rad
lib/std/lang/resolver/tests/regions.rad
lib/std/lang/resolver/opaqueTests.rad
lib/std/lang/il/publishedTests.rad

309	309		generator: &mut Generator,
310	310		func: &il::Fn,
311	311		config: &regalloc::TargetConfig,
312	312		storage: &Session 'scratch
313	313		) throws (alloc::AllocError) {
314		-	let ralloc = try regalloc::allocate(func, config, storage);
	314	+	let view = try il::published::publish(func, storage);
	315	+	let ralloc = try regalloc::allocate(&view, config, storage);
315	316		isel::selectFn(&mut generator.e, &ralloc, func);
316	317		}
317	318
318	319		/// Record an alternate name for the next function emitted.
319	320		export fn recordFunctionAlias(generator: &mut Generator, name: *[u8]) {

158	158		let func = il::Fn {
159	159		name: "p::pressure", params: &[], returnType: il::Type::W64, isExtern: false, isLeaf: true,
160	160		blocks: &[il::Block { label: "entry", params: &[], instrs: &mut [], locs: &[], preds: &[], loopDepth: 0 }],
161	161		};
162	162		let mut failed = false;
163		-	try regalloc::spill::analyze(&func, &live, 23, 11, 8, &bits) catch {
	163	+	let view = try! il::published::publish(&func, &bits);
	164	+	try regalloc::spill::analyze(&view, &live, 23, 11, 8, &bits) catch {
164	165		set failed = true;
165	166		};
166	167		try testing::expect(failed);
167	168		}
168	169		}

179	173		bitset::put(uses, reg.n);
180	174		}
181	175		}
182	176
183	177		/// Include all parameter, source, and destination registers in the entry count.
184		-	fn updateExtent(params: &[il::Param], instructions: &[il::Instr], max: &mut u32) throws (alloc::AllocError) {
	178	+	fn updateExtent 'input (params: &[il::Param], instructions: &[published::Instruction 'input], max: &mut u32) throws (alloc::AllocError) {
185	179		for p in params {
186	180		try updateMaxReg(p.value, max);
187	181		}
188	182		for i in 0..instructions.len {
189	183		let instr = &instructions[i];
190		-	let mut registers = il::registers(instr);
191		-	// Argument groups contain raw views into the function's IL storage.
192		-	unsafe {
193		-	while let reg = il::nextReg(&mut registers, instr) {
194		-	try updateMaxReg(reg, max);
195		-	}
	184	+	// Fixed operands precede the instruction's variable argument groups.
	185	+	for reg in published::registers(instr) {
	186	+	try updateMaxReg(reg, max);
196	187		}
197		-	if let dst = il::instrDst(*instr) {
	188	+	if let dst = published::destination(instr) {
198	189		try updateMaxReg(dst, max);
199	190		}
200	191		}
201	192		}
202	193

215	206		fn unionBlockLiveIn(target: u32, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
216	207		bitset::union_(liveOut, &liveIn[target * words..(target + 1) * words]);
217	208		}
218	209
219	210		/// Check if a register has any use after this instruction.
220		-	export unsafe fn hasLaterUse 'scratch (info: &LiveInfo 'scratch, func: &il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
	211	+	export fn hasLaterUse 'input 'scratch (info: &LiveInfo 'scratch, func: &published::Function 'input, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
221	212		let block = &func.blocks[blockIdx];
222	213
223	214		if bitset::contains(liveOutRow(info, blockIdx), reg.n) {
224	215		return true;
225	216		}
226		-	return usesRegisterAfter(block.instrs, instrIdx, reg);
	217	+	return usesRegisterAfter(block.instructions, instrIdx, reg);
227	218		}
228	219
229	220		/// Check if an instruction after the given index uses a specific register.
230		-	fn usesRegisterAfter(instructions: &[il::Instr], instrIdx: u32, reg: il::Reg) -> bool {
	221	+	fn usesRegisterAfter 'input (instructions: &[published::Instruction 'input], instrIdx: u32, reg: il::Reg) -> bool {
231	222		for i in (instrIdx + 1)..instructions.len {
232	223		let instr = &instructions[i];
233		-	let mut registers = il::registers(instr);
234		-	// Argument groups contain raw views into the function's IL storage.
235		-	unsafe {
236		-	while let source = il::nextReg(&mut registers, instr) {
237		-	if source.n == reg.n {
238		-	return true;
239		-	}
	224	+	// Fixed operands precede the instruction's variable argument groups.
	225	+	for source in published::registers(instr) {
	226	+	if source.n == reg.n {
	227	+	return true;
240	228		}
241	229		}
242	230		}
243	231		return false;
244	232		}

172	225		let function = il::Fn { name: "cycle", params: &[], returnType: il::Type::W64,
173	226		isExtern: false, isLeaf: true, blocks: &blocks[..] };
174	227		static DATA: [u8; 8192] = [0; 8192];
175	228		let mut arena = alloc::new(&mut DATA[..]);
176	229		use arena as analysis in {
177		-	let live = try! super::analyze(&function, &analysis);
	230	+	let live = try! analyze(&function, &analysis);
178	231		for index in 0..blocks.len {
179	232		try check(super::liveInRow(&live, index), false, false, index > 0 and index < 4);
180	233		try check(super::liveOutRow(&live, index), false, false, index <> 1 and index < 4);
181	234		}
182	235		}

17	17		export mod liveness;
18	18		export mod flow;
19	19		export mod spill;
20	20		export mod assign;
21	21
22		-	use std::lang::il;
	22	+	use std::lang::il::published;
23	23		use std::lang::alloc;
24	24
25	25		/// Target configuration for register allocation.
26	26		export record TargetConfig: Copy {
27	27		/// List of allocatable physical registers.

47	47
48	48		/// Run register allocation on a function.
49	49		///
50	50		/// Returns a mapping from SSA registers to physical registers, plus
51	51		/// spill information.
52		-	export unsafe fn allocate 'scratch (
53		-	func: &il::Fn,
	52	+	export fn allocate 'input 'scratch (
	53	+	func: &published::Function 'input,
54	54		config: &TargetConfig,
55	55		storage: &Session 'scratch
56	56		) -> AllocResult 'scratch throws (alloc::AllocError) {
57	57		// Phase 1: Liveness analysis.
58	58		let live = try liveness::analyze(func, storage);

5	5		//!
6	6		//! The IL is not modified. Instead, a mapping from SSA registers to physical
7	7		//! registers is produced for use by instruction selection.
8	8
9	9		use std::lang::il;
	10	+	use std::lang::il::published;
10	11		use std::lang::alloc;
11	12		use std::lang::gen;
12	13		use std::lang::gen::bitset;
13	14		use std::lang::gen::regalloc::liveness;
14	15		use std::lang::gen::regalloc::spill;

49	50		assignments: &'step mut [?gen::Reg],
50	51		spillInfo: &'step spill::SpillInfo 'scratch,
51	52		}
52	53
53	54		/// Compute register assignment.
54		-	export unsafe fn assign 'scratch (
55		-	func: &il::Fn,
	55	+	export fn assign 'input 'scratch (
	56	+	func: &published::Function 'input,
56	57		live: &liveness::LiveInfo 'scratch,
57	58		spillInfo: &spill::SpillInfo 'scratch,
58	59		config: &super::TargetConfig,
59	60		storage: &Session 'scratch
60	61		) -> AssignInfo 'scratch throws (alloc::AllocError) {
61	62		return try assignTables(func.params, func.blocks, live, spillInfo, config, storage);
62	63		}
63	64
64	65		/// Allocate register mappings for borrowed function parameter and block tables.
65		-	fn assignTables 'scratch (
	66	+	fn assignTables 'input 'scratch (
66	67		params: &[il::Param],
67		-	blocks: &[il::Block],
	68	+	blocks: &[published::Block 'input],
68	69		live: &liveness::LiveInfo 'scratch,
69	70		spillInfo: &spill::SpillInfo 'scratch,
70	71		config: &super::TargetConfig,
71	72		storage: &Session 'scratch,
72	73		) -> AssignInfo 'scratch throws (alloc::AllocError) {

119	120		allocatable,
120	121		calleeSaved: config.calleeSaved,
121	122		assignments: assignmentsRef,
122	123		spillInfo: spillRef,
123	124		};
124		-	unsafe {
125		-	assignBlock(block.params, block.instrs, &mut ctx, config);
126		-	}
	125	+	assignBlock(block.params, block.instructions, &mut ctx, config);
127	126		}
128	127		}
129	128		// Compute bitmask of used callee-saved registers.
130	129		let mut usedCalleeSaved: u32 = 0;
131	130		for i in 0..maxReg {

143	142		usedCalleeSaved,
144	143		};
145	144		}
146	145
147	146		/// Assign one block's source and destination registers in instruction order.
148		-	fn assignBlock 'scratch 'step (
	147	+	fn assignBlock 'input 'scratch 'step (
149	148		params: &[il::Param],
150		-	instructions: &[il::Instr],
	149	+	instructions: &[published::Instruction 'input],
151	150		ctx: &mut InstrCtx 'scratch 'step,
152	151		config: &super::TargetConfig,
153	152		) where 'scratch: 'step {
154	153		// Record every operand before allocation. Only current-block operands
155	154		// query this table, so every read is initialized by this scan.
156	155		// Entries for other registers need not be cleared between blocks.
157	156		for i in 0..instructions.len {
158	157		let instr = &instructions[i];
159		-	let mut registers = il::registers(instr);
160		-	unsafe {
161		-	while let reg = il::nextReg(&mut registers, instr) {
162		-	recordLastUse(reg, ctx.lastUse, i);
163		-	}
	158	+	for reg in published::registers(instr) {
	159	+	recordLastUse(reg, ctx.lastUse, i);
164	160		}
165	161		}
166	162
167	163		enterBlock(ctx.current, ctx.usedRegs, liveness::liveInRow(ctx.live, ctx.blockIdx), params, ctx.assignments, config, ctx.spillInfo);
168	164
169	165		// Process each instruction.
170	166		for i in 0..instructions.len {
171	167		let instr = &instructions[i];
172	168		set ctx.instrIdx = i;
173		-	let mut registers = il::registers(instr);
174		-	unsafe {
175		-	while let reg = il::nextReg(&mut registers, instr) {
176		-	processInstrReg(reg, ctx);
177		-	}
	169	+	for reg in published::registers(instr) {
	170	+	processInstrReg(reg, ctx);
178	171		}
179	172
180	173		// Allocate destination.
181		-	if let dst = il::instrDst(*instr) {
	174	+	if let dst = published::destination(instr) {
182	175		if dst.n < ctx.assignments.len and not spill::isSpilled(ctx.spillInfo, dst) {
183	176		set ctx.assignments[dst.n] = rallocReg(ctx.current, ctx.usedRegs, dst.n, ctx.allocatable, ctx.calleeSaved, ctx.spillInfo);
184	177		}
185	178		}
186	179		}

1	1		//! Owned control-flow topology for dataflow analysis.
2	2
3	3		use std::graph;
4	4		use std::lang::alloc;
5		-	use std::lang::il;
6		-
7		-	/// Largest successor count represented by a slice length.
8		-	constant MAX_SUCCESSORS: u32 = 0xffffffff;
	5	+	use std::lang::il::published;
9	6
10	7		/// Stable block identity and private successor storage.
11	8		export opaque record Block: 's + Copy {
12	9		/// Graph capability identity.
13	10		token: graph::Node 's,

23	20		frozen: graph::Frozen 's,
24	21		/// Stable block handles in function order.
25	22		blocks: &'s [Block 's],
26	23		}
27	24
28		-	/// Copy successor topology from valid IL into session-owned storage.
29		-	/// Instruction and switch tables must remain valid during this call.
30		-	export unsafe fn snapshot 's (blocks: &[il::Block], storage: &Session 's)
	25	+	/// Copy published successor topology into session-owned graph storage.
	26	+	export fn snapshot 'input 's (blocks: &[published::Block 'input], storage: &Session 's)
31	27		-> Flow 's throws (alloc::AllocError)
32	28		{
33	29		let mut builder = try graph::new(storage);
34	30		let none: [Block 's; 0] = [];
35	31		let empty: &'s [Block 's] = try storage.copy(&none[..]);

40	36		let entries = try storage.fill(first, blocks.len);
41	37		for i in 1..blocks.len {
42	38		set entries[i] = try reserve(&mut builder, i, empty, storage);
43	39		}
44	40		for block, i in blocks {
45		-	let instructions: &[il::Instr] = block.instrs;
	41	+	let instructions = block.instructions;
46	42		let mut links = empty;
47	43		if instructions.len > 0 {
48		-	let term = &instructions[instructions.len - 1];
49		-	match term {
50		-	case il::Instr::Jmp { target, .. } => {
51		-	set links = try storage.fill(entries[*target], 1);
52		-	},
53		-	case il::Instr::Br { thenTarget, elseTarget, .. } => {
54		-	let targets = try storage.fill(entries[*thenTarget], 2);
55		-	set targets[1] = entries[*elseTarget];
56		-	set links = &targets[..];
57		-	},
58		-	case il::Instr::Switch { defaultTarget, cases, .. } => {
59		-	let cases: &[il::SwitchCase] = *cases;
60		-	if cases.len == MAX_SUCCESSORS {
61		-	throw alloc::AllocError::OutOfMemory;
62		-	}
63		-	let targets = try storage.fill(entries[*defaultTarget], cases.len + 1);
64		-	for item, j in cases {
65		-	set targets[j + 1] = entries[item.target];
66		-	}
67		-	set links = &targets[..];
68		-	},
69		-	else => {},
	44	+	let targets = published::successors(&instructions[instructions.len - 1]);
	45	+	if targets.len > 0 {
	46	+	let successors = try storage.fill(entries[targets[0]], targets.len);
	47	+	for j in 1..targets.len {
	48	+	set successors[j] = entries[targets[j]];
	49	+	}
	50	+	set links = &successors[..];
70	51		}
71	52		}
72	53		try! define(&mut builder, entries[i], links);
73	54		}
74	55		return Flow 's { frozen: try! graph::freeze(builder), blocks: &entries[..] };

25	25		//! }
26	26
27	27		@test mod tests;
28	28
29	29		use std::lang::il;
	30	+	use std::lang::il::published;
30	31		use std::lang::alloc;
31	32		use std::lang::gen::bitset;
32	33		use super::flow;
33	34
34	35		/// Largest register index whose required entry count fits in u32.

51	52		/// Maximum register number used.
52	53		maxReg: u32,
53	54		}
54	55
55	56		/// Compute liveness by growing live sets until no live-in set changes.
56		-	export unsafe fn analyze 'scratch (func: &il::Fn, storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
	57	+	export fn analyze 'input 'scratch (func: &published::Function 'input, storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
57	58		return try analyzeTables(func.params, func.blocks, storage);
58	59		}
59	60
60	61		/// Allocate and compute live sets for borrowed function parameter and block tables.
61		-	fn analyzeTables 'scratch (params: &[il::Param], blocks: &[il::Block], storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
	62	+	fn analyzeTables 'input 'scratch (params: &[il::Param], blocks: &[published::Block 'input], storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {
62	63		let blockCount = blocks.len;
63	64		if blockCount == 0 {
64	65		let empty = try storage.fill(0 as u32, 0);
65	66		let frozen: &'scratch [u32] = &empty[..];
66	67		return LiveInfo 'scratch { liveIn: frozen, liveOut: frozen, defs: frozen, uses: frozen, words: 0, blockCount: 0, maxReg: 0 };
67	68		}
68	69
69	70		// Find max register number.
70	71		let mut maxReg: u32 = 0;
71		-	try updateExtent(params, &[], &mut maxReg);
	72	+	for parameter in params {
	73	+	try updateMaxReg(parameter.value, &mut maxReg);
	74	+	}
72	75		for b in 0..blockCount {
73	76		let block = &blocks[b];
74		-	unsafe {
75		-	try updateExtent(block.params, block.instrs, &mut maxReg);
76		-	}
	77	+	try updateExtent(block.params, block.instructions, &mut maxReg);
77	78		}
78	79		// Allocate one contiguous word matrix for each set class.
79	80		let words = bitset::wordsFor(maxReg);
80	81		let count64 = blockCount as u64 * words as u64;
81	82		if count64 > 0xFFFFFFFF {

88	89		let uses = try storage.fill(0 as u32, count);
89	90
90	91		// Compute local defs and uses for each block.
91	92		for b in 0..blockCount {
92	93		let block = &blocks[b];
93		-	unsafe {
94		-	computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
95		-	}
96		-	}
97		-	unsafe {
98		-	let topology = try flow::snapshot(blocks, storage);
99		-	propagateLiveness(&topology, blockCount, liveIn, liveOut, defs, uses, words);
	94	+	computeLocalDefsUses(block.params, block.instructions, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
100	95		}
	96	+	let topology = try flow::snapshot(blocks, storage);
	97	+	propagateLiveness(&topology, blockCount, liveIn, liveOut, defs, uses, words);
101	98		return LiveInfo 'scratch { liveIn: &liveIn[..], liveOut: &liveOut[..], defs: &defs[..], uses: &uses[..], words, blockCount, maxReg };
102	99		}
103	100
104	101		/// Propagate successor uses until every block's live-in row is stable.
105	102		fn propagateLiveness 'scratch (

151	148		}
152	149		return changed;
153	150		}
154	151
155	152		/// Compute local defs and uses for a single block.
156		-	fn computeLocalDefsUses(params: &[il::Param], instructions: &[il::Instr], defs: &mut [u32], uses: &mut [u32]) {
	153	+	fn computeLocalDefsUses 'input (params: &[il::Param], instructions: &[published::Instruction 'input], defs: &mut [u32], uses: &mut [u32]) {
157	154		for p in params {
158	155		bitset::put(defs, p.value.n);
159	156		}
160	157		for i in 0..instructions.len {
161	158		let instr = &instructions[i];
162		-	let mut registers = il::registers(instr);
163		-	// Argument groups contain raw views into the function's IL storage.
164		-	unsafe {
165		-	while let reg = il::nextReg(&mut registers, instr) {
166		-	addUse(reg, defs, uses);
167		-	}
	159	+	// Fixed operands precede the instruction's variable argument groups.
	160	+	for reg in published::registers(instr) {
	161	+	addUse(reg, defs, uses);
168	162		}
169	163
170		-	if let dst = il::instrDst(*instr) {
	164	+	if let dst = published::destination(instr) {
171	165		bitset::put(defs, dst.n);
172	166		}
173	167		}
174	168		}
175	169

1	1		//! Tests for liveness analysis.
2	2
3	3		use std::testing;
4	4		use std::lang::alloc;
5	5		use std::lang::il;
	6	+	use std::lang::il::published;
6	7		use std::lang::gen::bitset;
7	8		use std::lang::gen::regalloc::spill;
8	9		use std::lang::gen::regalloc::assign;
9	10		use std::lang::gen::regalloc;
10	11		use std::lang::gen::regalloc::flow;
11	12
	13	+	/// Publish fixture inputs outside the arena whose analysis capacity is tested.
	14	+	unsafe fn analyze 'scratch (function: &il::Fn, storage: &Session 'scratch)
	15	+	-> super::LiveInfo 'scratch throws (alloc::AllocError)
	16	+	{
	17	+	static DATA: [u8; 65536] = [0; 65536];
	18	+	let mut arena = alloc::new(&mut DATA[..]);
	19	+	use arena as inputs in {
	20	+	let view = try published::publish(function, &inputs);
	21	+	return try super::analyze(&view, storage);
	22	+	}
	23	+	}
	24	+
	25	+	/// Publish fixture inputs outside the arena whose spill capacity is tested.
	26	+	unsafe fn analyzeSpills 'scratch (function: &il::Fn, live: &super::LiveInfo 'scratch,
	27	+	numRegs: u32, numCalleeSaved: u32, slotSize: u32, storage: &Session 'scratch)
	28	+	-> spill::SpillInfo 'scratch throws (alloc::AllocError)
	29	+	{
	30	+	static DATA: [u8; 65536] = [0; 65536];
	31	+	let mut arena = alloc::new(&mut DATA[..]);
	32	+	use arena as inputs in {
	33	+	let view = try published::publish(function, &inputs);
	34	+	return try spill::analyze(&view, live, numRegs, numCalleeSaved, slotSize, storage);
	35	+	}
	36	+	}
	37	+
	38	+	/// Publish fixture inputs outside the arena whose assignment capacity is tested.
	39	+	unsafe fn assignRegisters 'scratch (function: &il::Fn, live: &super::LiveInfo 'scratch,
	40	+	spills: &spill::SpillInfo 'scratch, config: &regalloc::TargetConfig, storage: &Session 'scratch)
	41	+	-> assign::AssignInfo 'scratch throws (alloc::AllocError)
	42	+	{
	43	+	static DATA: [u8; 65536] = [0; 65536];
	44	+	let mut arena = alloc::new(&mut DATA[..]);
	45	+	use arena as inputs in {
	46	+	let view = try published::publish(function, &inputs);
	47	+	return try assign::assign(&view, live, spills, config, storage);
	48	+	}
	49	+	}
	50	+
	51	+	/// Publish CFG fixture inputs outside the graph allocation test arena.
	52	+	unsafe fn snapshot 'scratch (blocks: &[il::Block], storage: &Session 'scratch)
	53	+	-> flow::Flow 'scratch throws (alloc::AllocError)
	54	+	{
	55	+	let function = il::Fn { name: "topology", params: &[], returnType: il::Type::W64,
	56	+	isExtern: false, isLeaf: true, blocks: blocks as *unsafe [il::Block] };
	57	+	static DATA: [u8; 4096] = [0; 4096];
	58	+	let mut arena = alloc::new(&mut DATA[..]);
	59	+	use arena as inputs in {
	60	+	let view = try published::publish(&function, &inputs);
	61	+	return try flow::snapshot(view.blocks, storage);
	62	+	}
	63	+	}
	64	+
12	65		/// Frozen topology owns successor tables and preserves cyclic block identities.
13	66		@test unsafe fn testOwnedFlowSnapshot() throws (testing::TestError) {
14	67		let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut [] }];
15	68		let mut first = [il::Instr::Switch { val: il::Val::Imm(0), defaultTarget: 0,
16	69		defaultArgs: &mut [], cases: &mut cases[..] }];
17	70		let mut second = [il::Instr::Jmp { target: 0, args: &mut [] }];
18	71		let blocks = [block("first", &mut first[..]), block("second", &mut second[..])];
19	72		static DATA: [u8; 2048] = [0; 2048];
20	73		let mut arena = alloc::new(&mut DATA[..]);
21	74		use arena as storage in {
22		-	let frozen = try! flow::snapshot(&blocks[..], &storage);
	75	+	let frozen = try! snapshot(&blocks[..], &storage);
23	76		set cases[0].target = 0;
24	77		set first[0] = il::Instr::Ret { val: il::Val::Imm(0) };
25	78		set second[0] = il::Instr::Ret { val: il::Val::Imm(0) };
26	79		let successors = flow::successors(&frozen, 0);
27	80		assert successors.len == 2;

42	95		let mut succeeded = false;
43	96		for capacity in 0..257 {
44	97		static DATA: [u8; 256] = [0; 256];
45	98		let mut arena = alloc::new(&mut DATA[..capacity]);
46	99		use arena as storage in {
47		-	if let frozen = try? flow::snapshot(&blocks[..], &storage) {
	100	+	if let frozen = try? snapshot(&blocks[..], &storage) {
48	101		let links = flow::successors(&frozen, 0);
49	102		assert links.len == 1 and flow::index(links[0]) == 0;
50	103		set succeeded = true;
51	104		} else {
52	105		assert not succeeded;

72	125		let function = il::Fn { name: "empty", params: &[], returnType: il::Type::W64,
73	126		isExtern: false, isLeaf: true, blocks: &blocks[..count] };
74	127		static DATA: [u8; 1024] = [0; 1024];
75	128		let mut arena = alloc::new(&mut DATA[..]);
76	129		use arena as analysis in {
77		-	let live = try! super::analyze(&function, &analysis);
	130	+	let live = try! analyze(&function, &analysis);
78	131		assert live.blockCount == count;
79	132		assert live.maxReg == 0;
80	133		assert live.words == 0;
81	134		assert live.liveIn.len == 0 and live.liveOut.len == 0;
82	135		assert live.defs.len == 0 and live.uses.len == 0;
83		-	let spills = try! spill::analyze(&function, &live, 0, 0, 8, &analysis);
	136	+	let spills = try! analyzeSpills(&function, &live, 0, 0, 8, &analysis);
84	137		assert spills.maxReg == 0;
85	138		assert spills.frameSize == 0;
86	139		assert spills.slots.len == 0 and spills.calleeClass.len == 0;
87	140		let config = regalloc::TargetConfig { allocatable: &[], argRegs: &[], calleeSaved: &[], slotSize: 8 };
88		-	let assigned = try! assign::assign(&function, &live, &spills, &config, &analysis);
	141	+	let assigned = try! assignRegisters(&function, &live, &spills, &config, &analysis);
89	142		assert assigned.assignments.len == 0;
90	143		assert assigned.usedCalleeSaved == 0;
91	144		}
92	145		}
93	146		}

100	153		isExtern: false, isLeaf: true, blocks: &blocks[..] };
101	154		static DATA: [u8; 16] = [0; 16];
102	155		let mut arena = alloc::new(&mut DATA[..]);
103	156		let mut failed = false;
104	157		use arena as analysis in {
105		-	try super::analyze(&function, &analysis) catch {
	158	+	try analyze(&function, &analysis) catch {
106	159		set failed = true;
107	160		};
108	161		}
109	162		assert failed;
110	163		}

117	170		isExtern: false, isLeaf: true, blocks: &blocks[..] };
118	171		static DATA: [u8; 128] = [0; 128];
119	172		let mut arena = alloc::new(&mut DATA[..]);
120	173		let mut failed = false;
121	174		use arena as analysis in {
122		-	let live = try! super::analyze(&function, &analysis);
123		-	try spill::analyze(&function, &live, 0, 0, 8, &analysis) catch {
	175	+	let live = try! analyze(&function, &analysis);
	176	+	try analyzeSpills(&function, &live, 0, 0, 8, &analysis) catch {
124	177		set failed = true;
125	178		};
126	179		}
127	180		assert failed;
128	181		}

146	199		let function = il::Fn { name: "switch", params: &[], returnType: il::Type::W64,
147	200		isExtern: false, isLeaf: true, blocks: &blocks[..] };
148	201		static DATA: [u8; 8192] = [0; 8192];
149	202		let mut arena = alloc::new(&mut DATA[..]);
150	203		use arena as analysis in {
151		-	let live = try! super::analyze(&function, &analysis);
	204	+	let live = try! analyze(&function, &analysis);
152	205		try check(super::liveOutRow(&live, 0), count > 0, count == 3, true);
153	206		try check(super::liveInRow(&live, 0), count > 0, count == 3, true);
154	207		try check(super::liveOutRow(&live, 4), false, false, false);
155	208		}
156	209		}

202	255		let function = il::Fn { name: "later", params: &params[..], returnType: il::Type::W64,
203	256		isExtern: false, isLeaf: false, blocks: &blocks[..] };
204	257		static DATA: [u8; 8192] = [0; 8192];
205	258		let mut arena = alloc::new(&mut DATA[..]);
206	259		use arena as analysis in {
207		-	let live = try! super::analyze(&function, &analysis);
	260	+	let live = try! analyze(&function, &analysis);
	261	+	let view = try! published::publish(&function, &analysis);
208	262		for index in 0..entry.len {
209		-	assert super::hasLaterUse(&live, &function, 0, index, outgoing);
210		-	assert super::hasLaterUse(&live, &function, 0, index, argument) == (index == 0);
211		-	assert super::hasLaterUse(&live, &function, 0, index, result) == (index < 2);
212		-	assert not super::hasLaterUse(&live, &function, 0, index, unused);
	263	+	assert super::hasLaterUse(&live, &view, 0, index, outgoing);
	264	+	assert super::hasLaterUse(&live, &view, 0, index, argument) == (index == 0);
	265	+	assert super::hasLaterUse(&live, &view, 0, index, result) == (index < 2);
	266	+	assert not super::hasLaterUse(&live, &view, 0, index, unused);
213	267		}
214		-	assert not super::hasLaterUse(&live, &function, 1, 0, outgoing);
	268	+	assert not super::hasLaterUse(&live, &view, 1, 0, outgoing);
215	269		}
216	270		}
217	271
218	272		/// Local uses precede definitions, and block parameters define their registers.
219	273		@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {

233	287		let function = il::Fn { name: "local", params: &[], returnType: il::Type::W64,
234	288		isExtern: false, isLeaf: true, blocks: &blocks[..] };
235	289		static DATA: [u8; 8192] = [0; 8192];
236	290		let mut arena = alloc::new(&mut DATA[..]);
237	291		use arena as analysis in {
238		-	let live = try! super::analyze(&function, &analysis);
	292	+	let live = try! analyze(&function, &analysis);
239	293		try check(&live.defs[..live.words], true, true, true);
240	294		try check(&live.uses[..live.words], true, false, false);
241	295		try check(super::liveInRow(&live, 0), true, false, false);
242	296		try check(&live.defs[live.words..], false, false, false);
243	297		try check(&live.uses[live.words..], false, false, false);

257	311		let function = il::Fn { name: "extent", params: &[], returnType: il::Type::W64,
258	312		isExtern: false, isLeaf: true, blocks: &blocks[..] };
259	313		static DATA: [u8; 16384] = [0; 16384];
260	314		let mut arena = alloc::new(&mut DATA[..]);
261	315		use arena as analysis in {
262		-	let live = try super::analyze(&function, &analysis) catch {
	316	+	let live = try analyze(&function, &analysis) catch {
263	317		throw testing::TestError::Failed;
264	318		};
265	319		assert live.maxReg == index + 2;
266	320		assert bitset::contains(super::liveInRow(&live, 0), source.n);
267	321		assert bitset::contains(&live.defs[..], destination.n);

292	346		let function = il::Fn { name: "argument", params: &[], returnType: il::Type::W64,
293	347		isExtern: false, isLeaf: true, blocks: &blocks[..] };
294	348		static DATA: [u8; 32768] = [0; 32768];
295	349		let mut arena = alloc::new(&mut DATA[..]);
296	350		use arena as analysis in {
297		-	let live = try super::analyze(&function, &analysis) catch {
	351	+	let live = try analyze(&function, &analysis) catch {
298	352		assert index == 0xffffffff;
299	353		continue;
300	354		};
301	355		assert index <> 0xffffffff;
302	356		assert live.maxReg == index + 1;

354	408		let function = il::Fn { name: "offsets", params: &[], returnType: il::Type::W64,
355	409		isExtern: false, isLeaf: true, blocks: &blocks[..] };
356	410		static DATA: [u8; 16384] = [0; 16384];
357	411		let mut arena = alloc::new(&mut DATA[..]);
358	412		use arena as analysis in {
359		-	let live = try! super::analyze(&function, &analysis);
360		-	let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {
	413	+	let live = try! analyze(&function, &analysis);
	414	+	let info = try analyzeSpills(&function, &live, 0, 0, size, &analysis) catch {
361	415		assert size == 0x2aaaaaab;
362	416		continue;
363	417		};
364	418		assert size <= 0x2aaaaaaa;
365	419		assert info.slots[0] == 0;

383	437		let function = il::Fn { name: "frame", params: &[], returnType: il::Type::W64,
384	438		isExtern: false, isLeaf: true, blocks: &blocks[..] };
385	439		static DATA: [u8; 4096] = [0; 4096];
386	440		let mut arena = alloc::new(&mut DATA[..]);
387	441		use arena as analysis in {
388		-	let live = try! super::analyze(&function, &analysis);
389		-	let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {
	442	+	let live = try! analyze(&function, &analysis);
	443	+	let info = try analyzeSpills(&function, &live, 0, 0, size, &analysis) catch {
390	444		assert size > 0x7fffffff;
391	445		continue;
392	446		};
393	447		assert size == 0x7fffffff;
394	448		assert info.frameSize == 2147483647;

419	473		let function = il::Fn { name: "weighted", params: &[], returnType: il::Type::W64,
420	474		isExtern: false, isLeaf: true, blocks: &blocks[..] };
421	475		static DATA: [u8; 8192] = [0; 8192];
422	476		let mut arena = alloc::new(&mut DATA[..]);
423	477		use arena as analysis in {
424		-	let live = try! super::analyze(&function, &analysis);
425		-	let info = try! spill::analyze(&function, &live, 1, 0, 8, &analysis);
	478	+	let live = try! analyze(&function, &analysis);
	479	+	let info = try! analyzeSpills(&function, &live, 1, 0, 8, &analysis);
426	480		assert spill::isSpilled(&info, first) == (depth == 0);
427	481		assert spill::isSpilled(&info, second) == (depth > 0);
428	482		assert not spill::isSpilled(&info, temporary);
429	483		assert info.frameSize == 8;
430	484		}

455	509		isExtern: false, isLeaf: false, blocks: &blocks[..] };
456	510		for capacity in [0 as u32, 1, 2] {
457	511		static DATA: [u8; 8192] = [0; 8192];
458	512		let mut arena = alloc::new(&mut DATA[..]);
459	513		use arena as analysis in {
460		-	let live = try! super::analyze(&function, &analysis);
461		-	let info = try! spill::analyze(&function, &live, 8, capacity, 8, &analysis);
	514	+	let live = try! analyze(&function, &analysis);
	515	+	let info = try! analyzeSpills(&function, &live, 8, capacity, 8, &analysis);
462	516		assert spill::isSpilled(&info, first) == (capacity < 2);
463	517		assert spill::isSpilled(&info, second) == (capacity == 0);
464	518		assert not spill::isSpilled(&info, result);
465	519		assert not spill::isSpilled(&info, sum);
466	520		assert not spill::isSpilled(&info, total);

489	543		set function.params = &parameters[..];
490	544		}
491	545		static DATA: [u8; 16384] = [0; 16384];
492	546		let mut arena = alloc::new(&mut DATA[..]);
493	547		use arena as analysis in {
494		-	let live = try super::analyze(&function, &analysis) catch {
	548	+	let live = try analyze(&function, &analysis) catch {
495	549		assert index == 0xffffffff;
496	550		continue;
497	551		};
498	552		assert index == 16384;
499	553		assert live.maxReg == index + 1;

29	29		//!
30	30		//! * Spill slot assignments: SSA reg -> stack offset, `-1` if not spilled.
31	31		//! * Total frame size needed for spills.
32	32
33	33		use std::lang::il;
	34	+	use std::lang::il::published;
34	35		use std::lang::alloc;
35	36		use std::lang::gen::bitset;
36	37		use std::lang::gen::regalloc::liveness;
37	38
38	39		/// Maximum number of candidates for spill sorting.

73	74		reg: u32,
74	75		cost: u32,
75	76		}
76	77
77	78		/// Analyze a function and determine which values need spill slots.
78		-	export unsafe fn analyze 'scratch (
79		-	func: &il::Fn,
	79	+	export fn analyze 'input 'scratch (
	80	+	func: &published::Function 'input,
80	81		live: &liveness::LiveInfo 'scratch,
81	82		numRegs: u32,
82	83		numCalleeSaved: u32,
83	84		slotSize: u32,
84	85		storage: &Session 'scratch
85	86		) -> SpillInfo 'scratch throws (alloc::AllocError) {
86	87		return try analyzeBlocks(func.blocks, live, numRegs, numCalleeSaved, slotSize, storage);
87	88		}
88	89
89	90		/// Allocate spill storage and analyze pressure over a borrowed block table.
90		-	fn analyzeBlocks 'scratch (
91		-	blocks: &[il::Block],
	91	+	fn analyzeBlocks 'input 'scratch (
	92	+	blocks: &[published::Block 'input],
92	93		live: &liveness::LiveInfo 'scratch,
93	94		numRegs: u32,
94	95		numCalleeSaved: u32,
95	96		slotSize: u32,
96	97		storage: &Session 'scratch,