radiance · commit

compiler: Size register tables with checked extents

2f90db37943c2e6babfd088e56dd6612dd6e98141bfd79d6164ca1992beedaf1

Alexis Sellier committed 6 days ago 1 parent b213f338

lib/std/lang/gen/regalloc/liveness.rad +13 -21


use std::lang::il;
use std::lang::alloc;
use std::lang::gen::bitset;

/// Maximum number of SSA registers supported.
export constant MAX_SSA_REGS: u32 = 8192;
/// Largest register index whose required entry count fits in u32.
constant MAX_REGISTER_INDEX: u32 = 0xfffffffe;

/// Liveness information for a function.
export record LiveInfo: 'scratch + Copy {
    /// Per-block live-in words, stored in consecutive rows.
    liveIn: &'scratch [u32],

    }

    // Find max register number.
    let mut maxReg: u32 = 0;
    for p in func.params {
        set maxReg = maxRegNum(p.value.n, maxReg);
        try updateMaxReg(p.value, &mut maxReg);
    }
    for b in 0..blockCount {
        let block = &func.blocks[b];
        for p in block.params {
            set maxReg = maxRegNum(p.value.n, maxReg);
            try updateMaxReg(p.value, &mut maxReg);
        }
        for instr in block.instrs {
            let mut registers = il::registers(&instr);
            while let reg = il::nextReg(&mut registers, &instr) {
                updateMaxReg(reg, &mut maxReg);
                try updateMaxReg(reg, &mut maxReg);
            }
            if let dst = il::instrDst(instr) {
                set maxReg = maxRegNum(dst.n, maxReg);
                try updateMaxReg(dst, &mut maxReg);
            }
        }
    }
    if maxReg > MAX_SSA_REGS {
        throw alloc::AllocError::OutOfMemory;
    }
    // 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 {
        throw alloc::AllocError::OutOfMemory;

    if not bitset::contains(defs, reg.n) {
        bitset::put(uses, reg.n);
    }
}

/// Update the largest register number.
fn updateMaxReg(reg: il::Reg, max: &mut u32) {
    set *max = maxRegNum(reg.n, *max);
}

/// Return the larger of n+1 and current.
fn maxRegNum(n: u32, current: u32) -> u32 {
    if n >= MAX_SSA_REGS {
        return MAX_SSA_REGS + 1;
/// Retain the larger of the current entry count and the register index plus one.
fn updateMaxReg(reg: il::Reg, max: &mut u32) throws (alloc::AllocError) {
    if reg.n > MAX_REGISTER_INDEX {
        throw alloc::AllocError::OutOfMemory;
    }
    if n + 1 > current {
        return n + 1;
    let count = reg.n + 1;
    if count > *max {
        set *max = count;
    }
    return current;
}

/// Add successor live-in sets to the block's live-out set.
unsafe fn addSuccessorLiveIn(func: &il::Fn, block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
    if block.instrs.len == 0 {

lib/std/lang/gen/regalloc/liveness/tests.rad +107 -0


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


/// Construct a block whose instruction storage belongs to the caller.
unsafe fn block(name: *[u8], instructions: *unsafe mut [il::Instr]) -> il::Block {
    return il::Block { label: name, params: &[], instrs: instructions,
        locs: &[], preds: &[], loopDepth: 0 };
}

/// Liveness sizes its rows from register operands and definitions.
@test unsafe fn testLargeRegisterExtent() throws (testing::TestError) {
    for index in [8191 as u32, 8192, 8193, 16384] {
        let source = il::Reg { n: index };
        let destination = il::Reg { n: index + 1 };
        let mut instructions = [
            il::Instr::Copy { dst: destination, val: il::Val::Reg(source) },
            il::Instr::Ret { val: il::Val::Reg(destination) },
        ];
        let blocks = [block("entry", &mut instructions[..])];
        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 {
                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);
            assert not bitset::contains(super::liveInRow(&live, 0), destination.n);
        }
    }
}

/// An unrepresentable register extent fails before any bitset access.
@test unsafe fn testRegisterExtentOverflow() throws (testing::TestError) {
    for instruction in [
        il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0xffffffff }) },
        il::Instr::Copy { dst: il::Reg { n: 0xffffffff }, val: il::Val::Imm(0) },
    ] {
        let mut instructions = [instruction];
        let blocks = [block("entry", &mut instructions[..])];
        let function = il::Fn { name: "overflow", params: &[], returnType: il::Type::W64,
            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 {
                set failed = true;
            };
        }
        assert failed;
        assert arena.offset == 0;
    }
}

/// Check one bit in each word of a three-word row.
fn check(words: &[u32], first: bool, second: bool, third: bool) throws (testing::TestError) {
    try testing::expect(words.len == 3);
    try testing::expect(bitset::contains(words, 0) == first);
    try testing::expect(bitset::contains(words, 33) == second);
    try testing::expect(bitset::contains(words, 66) == third);
}

/// Spill frame sizes must fit their signed byte-offset representation.
@test unsafe fn testSpillFrameExtent() throws (testing::TestError) {
    for size in [0x7fffffff as u32, 0x80000000, 0xffffffff] {
        let value = il::Reg { n: 0 };
        let mut instructions = [
            il::Instr::Copy { dst: value, val: il::Val::Imm(1) },
            il::Instr::Ret { val: il::Val::Reg(value) },
        ];
        let blocks = [block("entry", &mut instructions[..])];
        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 {
                assert size > 0x7fffffff;
                continue;
            };
            assert size == 0x7fffffff;
            assert info.frameSize == 2147483647;
            assert info.slots[0] == 0;
        }
    }
}

/// Function and block parameter extents receive the same overflow checks.
@test unsafe fn testParameterRegisterExtent() throws (testing::TestError) {
    for index in [16384 as u32, 0xffffffff] {
        for isFunction in [false, true] {
            let parameters = [il::Param { value: il::Reg { n: index }, type: il::Type::W64 }];
            let mut instructions = [il::Instr::Ret { val: il::Val::Imm(0) }];
            let mut entry = block("entry", &mut instructions[..]);
            if not isFunction {
                set entry.params = &parameters[..];
            }
            let blocks = [entry];
            let mut function = il::Fn { name: "parameter", params: &[], returnType: il::Type::W64,
                isExtern: false, isLeaf: true, blocks: &blocks[..] };
            if isFunction {
                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 {
                    assert index == 0xffffffff;
                    continue;
                };
                assert index == 16384;
                assert live.maxReg == index + 1;
                assert bitset::contains(&live.defs[..], index) == not isFunction;
            }
        }
    }
}

@test unsafe fn testLoopLiveness() throws (testing::TestError) {
    let r0 = il::Reg { n: 0 };
    let r33 = il::Reg { n: 33 };
    let r66 = il::Reg { n: 66 };
    let mut entry = [

lib/std/lang/gen/regalloc/spill.rad +5 -0


/// Maximum number of candidates for spill sorting.
constant MAX_CANDIDATES: u32 = 256;
/// Maximum loop depth for cost weighting (2^10 = 1024).
constant MAX_LOOP_WEIGHT: u32 = 10;
/// Largest spill frame representable by signed byte offsets.
constant MAX_FRAME_SIZE: u32 = 0x7fffffff;

/// Spill cost for a single SSA register.
record SpillCost: Copy {
    /// Number of definitions (weighted by loop depth).
    defs: u32,

    // Phase 4: Assign stack slots to spilled values.
    let mut frameSize: i32 = 0;
    let mut it = bitset::iter(spilled);

    while let n = bitset::iterNext(&mut it, spilled) {
        if slotSize > MAX_FRAME_SIZE - frameSize as u32 {
            throw alloc::AllocError::OutOfMemory;
        }
        set slots[n] = frameSize;
        set frameSize += slotSize as i32;
    }
    return SpillInfo 'scratch { slots: &slots[..], frameSize, calleeClass: &calleeClass[..], maxReg };
}

test/driver +1 -0

            cat "$work/compile.log"
            exit 1
        fi
        grep -Fq 'selected: found 1024 test(s)' "$work/compile.log"
        test "$(grep -c 'call.*std::testing::test' "$work/compile.log")" -eq "$count"
        run "$inputs" "$count"
    else
        if compile "$inputs"; then
            echo 'driver: test discovery overflow unexpectedly succeeded'
            exit 1
        fi

163	160		if not bitset::contains(defs, reg.n) {
164	161		bitset::put(uses, reg.n);
165	162		}
166	163		}
167	164
168		-	/// Update the largest register number.
169		-	fn updateMaxReg(reg: il::Reg, max: &mut u32) {
170		-	set max = maxRegNum(reg.n, max);
171		-	}
172		-
173		-	/// Return the larger of n+1 and current.
174		-	fn maxRegNum(n: u32, current: u32) -> u32 {
175		-	if n >= MAX_SSA_REGS {
176		-	return MAX_SSA_REGS + 1;
	165	+	/// Retain the larger of the current entry count and the register index plus one.
	166	+	fn updateMaxReg(reg: il::Reg, max: &mut u32) throws (alloc::AllocError) {
	167	+	if reg.n > MAX_REGISTER_INDEX {
	168	+	throw alloc::AllocError::OutOfMemory;
177	169		}
178		-	if n + 1 > current {
179		-	return n + 1;
	170	+	let count = reg.n + 1;
	171	+	if count > *max {
	172	+	set *max = count;
180	173		}
181		-	return current;
182	174		}
183	175
184	176		/// Add successor live-in sets to the block's live-out set.
185	177		unsafe fn addSuccessorLiveIn(func: &il::Fn, block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
186	178		if block.instrs.len == 0 {

160	162		// Phase 4: Assign stack slots to spilled values.
161	163		let mut frameSize: i32 = 0;
162	164		let mut it = bitset::iter(spilled);
163	165
164	166		while let n = bitset::iterNext(&mut it, spilled) {
	167	+	if slotSize > MAX_FRAME_SIZE - frameSize as u32 {
	168	+	throw alloc::AllocError::OutOfMemory;
	169	+	}
165	170		set slots[n] = frameSize;
166	171		set frameSize += slotSize as i32;
167	172		}
168	173		return SpillInfo 'scratch { slots: &slots[..], frameSize, calleeClass: &calleeClass[..], maxReg };
169	174		}

28	28
29	29		use std::lang::il;
30	30		use std::lang::alloc;
31	31		use std::lang::gen::bitset;
32	32
33		-	/// Maximum number of SSA registers supported.
34		-	export constant MAX_SSA_REGS: u32 = 8192;
	33	+	/// Largest register index whose required entry count fits in u32.
	34	+	constant MAX_REGISTER_INDEX: u32 = 0xfffffffe;
35	35
36	36		/// Liveness information for a function.
37	37		export record LiveInfo: 'scratch + Copy {
38	38		/// Per-block live-in words, stored in consecutive rows.
39	39		liveIn: &'scratch [u32],

61	61		}
62	62
63	63		// Find max register number.
64	64		let mut maxReg: u32 = 0;
65	65		for p in func.params {
66		-	set maxReg = maxRegNum(p.value.n, maxReg);
	66	+	try updateMaxReg(p.value, &mut maxReg);
67	67		}
68	68		for b in 0..blockCount {
69	69		let block = &func.blocks[b];
70	70		for p in block.params {
71		-	set maxReg = maxRegNum(p.value.n, maxReg);
	71	+	try updateMaxReg(p.value, &mut maxReg);
72	72		}
73	73		for instr in block.instrs {
74	74		let mut registers = il::registers(&instr);
75	75		while let reg = il::nextReg(&mut registers, &instr) {
76		-	updateMaxReg(reg, &mut maxReg);
	76	+	try updateMaxReg(reg, &mut maxReg);
77	77		}
78	78		if let dst = il::instrDst(instr) {
79		-	set maxReg = maxRegNum(dst.n, maxReg);
	79	+	try updateMaxReg(dst, &mut maxReg);
80	80		}
81	81		}
82	82		}
83		-	if maxReg > MAX_SSA_REGS {
84		-	throw alloc::AllocError::OutOfMemory;
85		-	}
86	83		// Allocate one contiguous word matrix for each set class.
87	84		let words = bitset::wordsFor(maxReg);
88	85		let count64 = blockCount as u64 * words as u64;
89	86		if count64 > 0xFFFFFFFF {
90	87		throw alloc::AllocError::OutOfMemory;

2	2
3	3		use std::testing;
4	4		use std::lang::alloc;
5	5		use std::lang::il;
6	6		use std::lang::gen::bitset;
	7	+	use std::lang::gen::regalloc::spill;
7	8
8	9
9	10		/// Construct a block whose instruction storage belongs to the caller.
10	11		unsafe fn block(name: [u8], instructions: unsafe mut [il::Instr]) -> il::Block {
11	12		return il::Block { label: name, params: &[], instrs: instructions,
12	13		locs: &[], preds: &[], loopDepth: 0 };
13	14		}
14	15
	16	+	/// Liveness sizes its rows from register operands and definitions.
	17	+	@test unsafe fn testLargeRegisterExtent() throws (testing::TestError) {
	18	+	for index in [8191 as u32, 8192, 8193, 16384] {
	19	+	let source = il::Reg { n: index };
	20	+	let destination = il::Reg { n: index + 1 };
	21	+	let mut instructions = [
	22	+	il::Instr::Copy { dst: destination, val: il::Val::Reg(source) },
	23	+	il::Instr::Ret { val: il::Val::Reg(destination) },
	24	+	];
	25	+	let blocks = [block("entry", &mut instructions[..])];
	26	+	let function = il::Fn { name: "extent", params: &[], returnType: il::Type::W64,
	27	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	28	+	static DATA: [u8; 16384] = [0; 16384];
	29	+	let mut arena = alloc::new(&mut DATA[..]);
	30	+	use arena as analysis in {
	31	+	let live = try super::analyze(&function, &analysis) catch {
	32	+	throw testing::TestError::Failed;
	33	+	};
	34	+	assert live.maxReg == index + 2;
	35	+	assert bitset::contains(super::liveInRow(&live, 0), source.n);
	36	+	assert bitset::contains(&live.defs[..], destination.n);
	37	+	assert not bitset::contains(super::liveInRow(&live, 0), destination.n);
	38	+	}
	39	+	}
	40	+	}
	41	+
	42	+	/// An unrepresentable register extent fails before any bitset access.
	43	+	@test unsafe fn testRegisterExtentOverflow() throws (testing::TestError) {
	44	+	for instruction in [
	45	+	il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0xffffffff }) },
	46	+	il::Instr::Copy { dst: il::Reg { n: 0xffffffff }, val: il::Val::Imm(0) },
	47	+	] {
	48	+	let mut instructions = [instruction];
	49	+	let blocks = [block("entry", &mut instructions[..])];
	50	+	let function = il::Fn { name: "overflow", params: &[], returnType: il::Type::W64,
	51	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	52	+	static DATA: [u8; 1024] = [0; 1024];
	53	+	let mut arena = alloc::new(&mut DATA[..]);
	54	+	let mut failed = false;
	55	+	use arena as analysis in {
	56	+	try super::analyze(&function, &analysis) catch {
	57	+	set failed = true;
	58	+	};
	59	+	}
	60	+	assert failed;
	61	+	assert arena.offset == 0;
	62	+	}
	63	+	}
	64	+
15	65		/// Check one bit in each word of a three-word row.
16	66		fn check(words: &[u32], first: bool, second: bool, third: bool) throws (testing::TestError) {
17	67		try testing::expect(words.len == 3);
18	68		try testing::expect(bitset::contains(words, 0) == first);
19	69		try testing::expect(bitset::contains(words, 33) == second);
20	70		try testing::expect(bitset::contains(words, 66) == third);
21	71		}
22	72
	73	+	/// Spill frame sizes must fit their signed byte-offset representation.
	74	+	@test unsafe fn testSpillFrameExtent() throws (testing::TestError) {
	75	+	for size in [0x7fffffff as u32, 0x80000000, 0xffffffff] {
	76	+	let value = il::Reg { n: 0 };
	77	+	let mut instructions = [
	78	+	il::Instr::Copy { dst: value, val: il::Val::Imm(1) },
	79	+	il::Instr::Ret { val: il::Val::Reg(value) },
	80	+	];
	81	+	let blocks = [block("entry", &mut instructions[..])];
	82	+	let function = il::Fn { name: "frame", params: &[], returnType: il::Type::W64,
	83	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	84	+	static DATA: [u8; 4096] = [0; 4096];
	85	+	let mut arena = alloc::new(&mut DATA[..]);
	86	+	use arena as analysis in {
	87	+	let live = try! super::analyze(&function, &analysis);
	88	+	let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {
	89	+	assert size > 0x7fffffff;
	90	+	continue;
	91	+	};
	92	+	assert size == 0x7fffffff;
	93	+	assert info.frameSize == 2147483647;
	94	+	assert info.slots[0] == 0;
	95	+	}
	96	+	}
	97	+	}
	98	+
	99	+	/// Function and block parameter extents receive the same overflow checks.
	100	+	@test unsafe fn testParameterRegisterExtent() throws (testing::TestError) {
	101	+	for index in [16384 as u32, 0xffffffff] {
	102	+	for isFunction in [false, true] {
	103	+	let parameters = [il::Param { value: il::Reg { n: index }, type: il::Type::W64 }];
	104	+	let mut instructions = [il::Instr::Ret { val: il::Val::Imm(0) }];
	105	+	let mut entry = block("entry", &mut instructions[..]);
	106	+	if not isFunction {
	107	+	set entry.params = &parameters[..];
	108	+	}
	109	+	let blocks = [entry];
	110	+	let mut function = il::Fn { name: "parameter", params: &[], returnType: il::Type::W64,
	111	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	112	+	if isFunction {
	113	+	set function.params = &parameters[..];
	114	+	}
	115	+	static DATA: [u8; 16384] = [0; 16384];
	116	+	let mut arena = alloc::new(&mut DATA[..]);
	117	+	use arena as analysis in {
	118	+	let live = try super::analyze(&function, &analysis) catch {
	119	+	assert index == 0xffffffff;
	120	+	continue;
	121	+	};
	122	+	assert index == 16384;
	123	+	assert live.maxReg == index + 1;
	124	+	assert bitset::contains(&live.defs[..], index) == not isFunction;
	125	+	}
	126	+	}
	127	+	}
	128	+	}
	129	+
23	130		@test unsafe fn testLoopLiveness() throws (testing::TestError) {
24	131		let r0 = il::Reg { n: 0 };
25	132		let r33 = il::Reg { n: 33 };
26	133		let r66 = il::Reg { n: 66 };
27	134		let mut entry = [

37	37
38	38		/// Maximum number of candidates for spill sorting.
39	39		constant MAX_CANDIDATES: u32 = 256;
40	40		/// Maximum loop depth for cost weighting (2^10 = 1024).
41	41		constant MAX_LOOP_WEIGHT: u32 = 10;
	42	+	/// Largest spill frame representable by signed byte offsets.
	43	+	constant MAX_FRAME_SIZE: u32 = 0x7fffffff;
42	44
43	45		/// Spill cost for a single SSA register.
44	46		record SpillCost: Copy {
45	47		/// Number of definitions (weighted by loop depth).
46	48		defs: u32,

72	72		cat "$work/compile.log"
73	73		exit 1
74	74		fi
75	75		grep -Fq 'selected: found 1024 test(s)' "$work/compile.log"
76	76		test "$(grep -c 'call.*std::testing::test' "$work/compile.log")" -eq "$count"
	77	+	run "$inputs" "$count"
77	78		else
78	79		if compile "$inputs"; then
79	80		echo 'driver: test discovery overflow unexpectedly succeeded'
80	81		exit 1
81	82		fi