radiance · commit

compiler: Check liveness allocation and analysis pipeline

4a63458bf878c8820f6451d6d24f755b1d5cb9becacb302e647294946313e8bb

Alexis Sellier committed 6 days ago 1 parent 989da8bf

lib/std/lang/gen/regalloc/liveness.rad +16 -7

    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) {
    let blockCount = func.blocks.len;
    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) {
    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(func.params, &[], &mut maxReg);
    try updateExtent(params, &[], &mut maxReg);
    for b in 0..blockCount {
        let block = &func.blocks[b];
        try updateExtent(block.params, block.instrs, &mut maxReg);
        let block = &blocks[b];
        unsafe {
            try updateExtent(block.params, block.instrs, &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 defs = try storage.fill(0 as u32, count);
    let uses = try storage.fill(0 as u32, count);

    // Compute local defs and uses for each block.
    for b in 0..blockCount {
        let block = &func.blocks[b];
        computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
        let block = &blocks[b];
        unsafe {
            computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
        }
    }
    propagateLiveness(func.blocks, liveIn, liveOut, defs, uses, words);
    propagateLiveness(blocks, 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(

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

unsafe fn block(name: *[u8], instructions: *unsafe mut [il::Instr]) -> il::Block {
    return il::Block { label: name, params: &[], instrs: instructions,
        locs: &[], preds: &[], loopDepth: 0 };
}

/// Empty functions and register-free blocks produce empty liveness matrices.
@test unsafe fn testEmptyLivenessStorage() throws (testing::TestError) {
    let mut instructions = [il::Instr::Ret { val: il::Val::Imm(0) }];
    let blocks = [block("entry", &mut instructions[..])];
    for count in [0 as u32, 1] {
        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);
            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;
        }
    }
}

/// Insufficient matrix storage reports an allocation error.
@test unsafe fn testLivenessStorageExhaustion() throws (testing::TestError) {
    let mut instructions = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];
    let blocks = [block("entry", &mut instructions[..])];
    let function = il::Fn { name: "storage", params: &[], returnType: il::Type::W64,
        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 {
            set failed = true;
        };
    }
    assert failed;
}

/// Switch successors merge distinct words and tolerate repeated destinations.
@test unsafe fn testSwitchSuccessorLiveness() throws (testing::TestError) {
    for count in [0 as u32, 1, 3] {
        let mut cases = [
            il::SwitchCase { value: 0, target: 1, args: &mut [] },

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

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

11	11		unsafe fn block(name: [u8], instructions: unsafe mut [il::Instr]) -> il::Block {
12	12		return il::Block { label: name, params: &[], instrs: instructions,
13	13		locs: &[], preds: &[], loopDepth: 0 };
14	14		}
15	15
	16	+	/// Empty functions and register-free blocks produce empty liveness matrices.
	17	+	@test unsafe fn testEmptyLivenessStorage() throws (testing::TestError) {
	18	+	let mut instructions = [il::Instr::Ret { val: il::Val::Imm(0) }];
	19	+	let blocks = [block("entry", &mut instructions[..])];
	20	+	for count in [0 as u32, 1] {
	21	+	let function = il::Fn { name: "empty", params: &[], returnType: il::Type::W64,
	22	+	isExtern: false, isLeaf: true, blocks: &blocks[..count] };
	23	+	static DATA: [u8; 1024] = [0; 1024];
	24	+	let mut arena = alloc::new(&mut DATA[..]);
	25	+	use arena as analysis in {
	26	+	let live = try! super::analyze(&function, &analysis);
	27	+	assert live.blockCount == count;
	28	+	assert live.maxReg == 0;
	29	+	assert live.words == 0;
	30	+	assert live.liveIn.len == 0 and live.liveOut.len == 0;
	31	+	assert live.defs.len == 0 and live.uses.len == 0;
	32	+	}
	33	+	}
	34	+	}
	35	+
	36	+	/// Insufficient matrix storage reports an allocation error.
	37	+	@test unsafe fn testLivenessStorageExhaustion() throws (testing::TestError) {
	38	+	let mut instructions = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];
	39	+	let blocks = [block("entry", &mut instructions[..])];
	40	+	let function = il::Fn { name: "storage", params: &[], returnType: il::Type::W64,
	41	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	42	+	static DATA: [u8; 16] = [0; 16];
	43	+	let mut arena = alloc::new(&mut DATA[..]);
	44	+	let mut failed = false;
	45	+	use arena as analysis in {
	46	+	try super::analyze(&function, &analysis) catch {
	47	+	set failed = true;
	48	+	};
	49	+	}
	50	+	assert failed;
	51	+	}
	52	+
16	53		/// Switch successors merge distinct words and tolerate repeated destinations.
17	54		@test unsafe fn testSwitchSuccessorLiveness() throws (testing::TestError) {
18	55		for count in [0 as u32, 1, 3] {
19	56		let mut cases = [
20	57		il::SwitchCase { value: 0, target: 1, args: &mut [] },