compiler: Return register allocation capacity failures

85034f8f30056fd13c12becfbbadfa51f35055d34cc8b8cdc3131d7f550a7d65
Return allocation errors when SSA register numbering or spill candidate storage
exceeds fixed limits. Propagate those errors through liveness and spill analysis
instead of relying on assertions. Add boundary regressions for both limits.
Alexis Sellier committed ago 1 parent 3aa3f740
lib/std/arch/rv64/tests.rad +60 -0
3 3
//! These tests verify that instruction encodings match the RISC-V specification
4 4
//! by comparing against known-good values.
5 5
6 6
use std::testing;
7 7
use std::lang::alloc;
8 +
use std::lang::il;
9 +
use std::lang::gen::bitset;
10 +
use std::lang::gen::regalloc;
11 +
use std::lang::gen::regalloc::liveness;
8 12
use std::collections::dict;
9 13
10 14
use super::encode;
11 15
use super::asm;
12 16
13 17
static ASSEMBLY_ARENA_STORAGE: [u8; 16777216] = [0; 16777216];
14 18
static ASSEMBLY_TEXT_STORAGE: [u32; 2] = [0; 2];
15 19
20 +
/// Scratch storage for register limit checks.
21 +
static REGISTER_SCRATCH: [u8; 65536] = [0; 65536];
22 +
23 +
/// Register limits apply to parameters, instruction operands, and destinations.
24 +
@test unsafe fn testRegisterLimit() throws (testing::TestError) {
25 +
    for number in [0, liveness::MAX_SSA_REGS - 1, liveness::MAX_SSA_REGS, 0xffffffff] {
26 +
        let reg = il::Reg { n: number };
27 +
        let params = [il::Param { value: reg, type: il::Type::W64 }];
28 +
        let mut operand = [il::Instr::Ret { val: il::Val::Reg(reg) }];
29 +
        let mut destination = [il::Instr::Copy { dst: reg, val: il::Val::Imm(0) }];
30 +
31 +
        checkRegisterLimit(number, &params[..], &[], &mut []);
32 +
        checkRegisterLimit(number, &[], &params[..], &mut []);
33 +
        checkRegisterLimit(number, &[], &[], &mut operand[..]);
34 +
        checkRegisterLimit(number, &[], &[], &mut destination[..]);
35 +
    }
36 +
}
37 +
38 +
/// Check the required register count and reject unsupported numbers before allocation.
39 +
unsafe fn checkRegisterLimit(number: u32, params: *unsafe [il::Param], blockParams: *unsafe [il::Param], instrs: *unsafe mut [il::Instr]) {
40 +
    let mut arena = alloc::new(&mut REGISTER_SCRATCH[..]);
41 +
    let func = il::Fn {
42 +
        name: "limit", params, returnType: il::Type::W64, isExtern: false, isLeaf: true,
43 +
        blocks: &[il::Block { label: "entry", params: blockParams, instrs, locs: &[], preds: &[], loopDepth: 0 }],
44 +
    };
45 +
    let live = try liveness::analyze(&func, &mut arena) catch {
46 +
        assert number >= liveness::MAX_SSA_REGS;
47 +
        assert arena.offset == 0;
48 +
        return;
49 +
    };
50 +
    assert number < liveness::MAX_SSA_REGS;
51 +
    assert live.maxReg == number + 1;
52 +
}
53 +
16 54
/// Helper to check encoding equals expected value.
17 55
fn expectEncoding(actual: u32, expected: u32) throws (testing::TestError) {
18 56
    try testing::expect(actual == expected);
19 57
}
20 58
551 589
    try testing::expect(encode::isJumpImm(1048574));    // Max positive even
552 590
    try testing::expect(encode::isJumpImm(-1048576));   // Min negative
553 591
    try testing::expectNot(encode::isJumpImm(1));       // Must be even
554 592
    try testing::expectNot(encode::isJumpImm(1048576)); // Out of range
555 593
}
594 +
595 +
/// Excess live values return an error before the spill candidate table overflows.
596 +
@test unsafe fn testSpillCandidateLimit() throws (testing::TestError) {
597 +
    let mut arena = alloc::new(&mut REGISTER_SCRATCH[..]);
598 +
    let mut liveSet = try! bitset::allocate(&mut arena, 257);
599 +
    for i in 0..257 {
600 +
        bitset::put(&mut liveSet, i);
601 +
    }
602 +
    let mut out = [liveSet];
603 +
    let live = regalloc::liveness::LiveInfo {
604 +
        liveIn: &mut [], liveOut: &mut out[..], defs: &mut [], uses: &mut [], blockCount: 1, maxReg: 257,
605 +
    };
606 +
    let func = il::Fn {
607 +
        name: "pressure", params: &[], returnType: il::Type::W64, isExtern: false, isLeaf: true,
608 +
        blocks: &[il::Block { label: "entry", params: &[], instrs: &mut [], locs: &[], preds: &[], loopDepth: 0 }],
609 +
    };
610 +
    let mut failed = false;
611 +
    try regalloc::spill::analyze(&func, &live, 23, 11, 8, &mut arena) catch {
612 +
        set failed = true;
613 +
    };
614 +
    assert failed;
615 +
}
lib/std/lang/gen/regalloc/liveness.rad +18 -19
73 73
            maxReg: 0,
74 74
        };
75 75
    }
76 76
77 77
    // Find max register number.
78 -
    let mut maxReg: u32 = 0;
78 +
    let mut registerCount: u64 = 0;
79 79
    for p in func.params {
80 -
        set maxReg = maxRegNum(p.value.n, maxReg);
80 +
        countRegisters(p.value, &mut registerCount);
81 81
    }
82 82
    for b in 0..blockCount {
83 83
        let block = &func.blocks[b];
84 84
        for p in block.params {
85 -
            set maxReg = maxRegNum(p.value.n, maxReg);
85 +
            countRegisters(p.value, &mut registerCount);
86 86
        }
87 87
        for i in 0..block.instrs.len {
88 -
            il::forEachReg(block.instrs[i], maxRegCallback, &mut maxReg as &mut opaque);
88 +
            il::forEachReg(block.instrs[i], countRegistersCallback, &mut registerCount as &mut opaque);
89 89
            if let dst = il::instrDst(block.instrs[i]) {
90 -
                set maxReg = maxRegNum(dst.n, maxReg);
90 +
                countRegisters(dst, &mut registerCount);
91 91
            }
92 92
        }
93 93
    }
94 -
    assert maxReg <= MAX_SSA_REGS, "analyze: maximum SSA registers exceeded";
94 +
    if registerCount > MAX_SSA_REGS as u64 {
95 +
        throw alloc::AllocError::OutOfMemory;
96 +
    }
97 +
    let maxReg = registerCount as u32;
95 98
    // Allocate per-block bitsets.
96 99
    let liveIn = try alloc::allocRawSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *unsafe mut [bitset::Bitset];
97 100
    let liveOut = try alloc::allocRawSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *unsafe mut [bitset::Bitset];
98 101
    let defs = try alloc::allocRawSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *unsafe mut [bitset::Bitset];
99 102
    let uses = try alloc::allocRawSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *unsafe mut [bitset::Bitset];
178 181
    if not bitset::contains(c.defs, reg.n) {
179 182
        bitset::put(c.uses, reg.n);
180 183
    }
181 184
}
182 185
183 -
/// Callback for [`il::forEachReg`]: updates max register number.
184 -
unsafe fn maxRegCallback(reg: il::Reg, ctx: &mut opaque) {
185 -
    updateMaxReg(reg, ctx as &mut u32);
186 -
}
187 -
188 -
/// Update the largest register number.
189 -
fn updateMaxReg(reg: il::Reg, max: &mut u32) {
190 -
    set *max = maxRegNum(reg.n, *max);
186 +
/// Callback for [`il::forEachReg`]: includes the operand in the register count.
187 +
unsafe fn countRegistersCallback(reg: il::Reg, ctx: &mut opaque) {
188 +
    countRegisters(reg, ctx as &mut u64);
191 189
}
192 190
193 -
/// Return the larger of n+1 and current.
194 -
fn maxRegNum(n: u32, current: u32) -> u32 {
195 -
    if n + 1 > current {
196 -
        return n + 1;
191 +
/// Include a register in the required bitset size.
192 +
/// A 64-bit count can represent one past every 32-bit register number.
193 +
fn countRegisters(reg: il::Reg, count: &mut u64) {
194 +
    let next = reg.n as u64 + 1;
195 +
    if next > *count {
196 +
        set *count = next;
197 197
    }
198 -
    return current;
199 198
}
200 199
201 200
/// Add successor live-in sets to the block's live-out set.
202 201
unsafe fn addSuccessorLiveIn(func: *unsafe il::Fn, block: *unsafe il::Block, liveIn: *unsafe [bitset::Bitset], liveOut: *unsafe mut bitset::Bitset) {
203 202
    if block.instrs.len == 0 {
lib/std/lang/gen/regalloc/spill.rad +13 -8
126 126
        while i > 0 {
127 127
            set i -= 1;
128 128
            let instr = block.instrs[i];
129 129
130 130
            // Limit register pressure before processing this instruction.
131 -
            limitPressure(&mut scratch, &mut spilled, costs, numRegs);
131 +
            try limitPressure(&mut scratch, &mut spilled, costs, numRegs);
132 132
133 133
            // Enforce cross-call pressure at call sites.
134 134
            if il::isCall(instr) {
135 -
                limitCrossCallPressure(
135 +
                try limitCrossCallPressure(
136 136
                    &mut scratch, &mut spilled, costs,
137 137
                    &mut calleeClass, numCalleeSaved, il::instrDst(instr)
138 138
                );
139 139
            }
140 140
            // Remove definition from live set.
143 143
            }
144 144
            // Add uses to live set.
145 145
            il::forEachReg(instr, addRegToSetCallback, &mut scratch as &mut opaque);
146 146
        }
147 147
        // Also limit pressure at block entry.
148 -
        limitPressure(&mut scratch, &mut spilled, costs, numRegs);
148 +
        try limitPressure(&mut scratch, &mut spilled, costs, numRegs);
149 149
    }
150 150
151 151
    // Phase 3: Enforce global callee-class limit.
152 152
    // The per-call-site limit may leave the callee-class set larger than
153 153
    // `numCalleeSaved` when different call sites keep different subsets.
233 233
        bitset::clear(source, c.entries[i].reg);
234 234
    }
235 235
}
236 236
237 237
/// Collect all values from a bitset into a candidates buffer with their costs.
238 -
unsafe fn collectCandidates(bs: &bitset::Bitset, costs: *unsafe [SpillCost]) -> Candidates {
238 +
unsafe fn collectCandidates(bs: &bitset::Bitset, costs: *unsafe [SpillCost]) -> Candidates throws (alloc::AllocError) {
239 239
    let mut c = Candidates { entries: undefined, n: 0 };
240 240
    let mut it = bitset::iter(bs);
241 241
    while let reg = bitset::iterNext(&mut it) {
242 -
        assert c.n < MAX_CANDIDATES, "collectCandidates: too many live values";
242 +
        if c.n == MAX_CANDIDATES {
243 +
            throw alloc::AllocError::OutOfMemory;
244 +
        }
243 245
        if reg < costs.len {
244 246
            set c.entries[c.n] = CostEntry { reg, cost: costs[reg].defs + costs[reg].uses };
245 247
            set c.n += 1;
246 248
        }
247 249
    }
252 254
unsafe fn limitPressure(
253 255
    live: &mut bitset::Bitset,
254 256
    spilled: &mut bitset::Bitset,
255 257
    costs: *unsafe [SpillCost],
256 258
    numRegs: u32
257 -
) {
259 +
) throws (alloc::AllocError) {
258 260
    let liveCount = bitset::count(live);
259 261
    if liveCount <= numRegs {
260 262
        return;
261 263
    }
262 -
    let mut c = collectCandidates(live, costs);
264 +
    let mut c = try collectCandidates(live, costs);
263 265
    spillCheapest(&mut c, liveCount - numRegs, live, spilled);
264 266
}
265 267
266 268
/// Check whether an SSA register is the destination of a call instruction.
267 269
fn isCallDst(callDst: ?il::Reg, n: u32) -> bool {
281 283
    spilled: &mut bitset::Bitset,
282 284
    costs: *unsafe [SpillCost],
283 285
    calleeClass: &mut bitset::Bitset,
284 286
    numCalleeSaved: u32,
285 287
    callDst: ?il::Reg
286 -
) {
288 +
) throws (alloc::AllocError) {
287 289
    // Collect crossing candidates: live values excluding the call destination.
288 290
    let mut candidates: [CostEntry; 256] = undefined;
289 291
    let mut numCandidates: u32 = 0;
290 292
    let mut it = bitset::iter(live);
291 293
    while let n = bitset::iterNext(&mut it) {
292 294
        if not isCallDst(callDst, n) and n < costs.len {
295 +
            if numCandidates == MAX_CANDIDATES {
296 +
                throw alloc::AllocError::OutOfMemory;
297 +
            }
293 298
            set candidates[numCandidates] = CostEntry {
294 299
                reg: n,
295 300
                cost: costs[n].defs + costs[n].uses,
296 301
            };
297 302
            set numCandidates += 1;