radiance · commit

compiler: Check liveness fixed-point propagation

1671d5e00a1c3a02f66ee10466961853881fecbeb5a156411a11ca208b3f3700

Alexis Sellier committed 6 days ago 1 parent 891b61ae

lib/std/lang/gen/regalloc/liveness.rad +18 -4

    // 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]);
    }
    propagateLiveness(func.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(
    blocks: &[il::Block],
    liveIn: &mut [u32],
    liveOut: &mut [u32],
    defs: &[u32],
    uses: &[u32],
    words: u32,
) {
    // Live sets grow monotonically from empty sets; no scratch set is needed.
    let mut changed = true;

    while changed {
        set changed = false;

        // Process blocks in reverse order (approximates post-order).
        let mut b = blockCount;
        let mut b = blocks.len;
        while b > 0 {
            set b -= 1;
            let block = &func.blocks[b];
            let block = &blocks[b];

            // Add successor live-in sets directly to this block's live-out set.
            addSuccessorLiveIn(block, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);
            unsafe {
                addSuccessorLiveIn(block, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);
            }

            if computeAndUpdateLiveIn(&mut liveIn[b * words..(b + 1) * words], &liveOut[b * words..(b + 1) * words], &defs[b * words..(b + 1) * words], &uses[b * words..(b + 1) * words]) {
                set changed = true;
            }
        }
    }
    return LiveInfo 'scratch { liveIn: &liveIn[..], liveOut: &liveOut[..], defs: &defs[..], uses: &uses[..], words, blockCount, maxReg };
}

/// Compute `liveIn = uses | (liveOut - defs)` and update `dst`.
/// Returns `true` if `dst` changed. Combined loop avoids multiple passes.
fn computeAndUpdateLiveIn(

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

            try check(super::liveOutRow(&live, 4), false, false, false);
        }
    }
}

/// A cyclic graph propagates uses against block order until all rows stabilize.
@test unsafe fn testDelayedCyclicPropagation() throws (testing::TestError) {
    let value = il::Reg { n: 66 };
    let mut entry = [il::Instr::Copy { dst: value, val: il::Val::Imm(7) },
        il::Instr::Jmp { target: 3, args: &mut [] }];
    let mut exit = [il::Instr::Ret { val: il::Val::Reg(value) }];
    let mut bridge = [il::Instr::Jmp { target: 1, args: &mut [] }];
    let mut cycle = [il::Instr::Br { op: il::CmpOp::Eq, typ: il::Type::W64,
        a: il::Val::Imm(0), b: il::Val::Imm(1), thenTarget: 3, thenArgs: &mut [],
        elseTarget: 2, elseArgs: &mut [] }];
    let blocks = [block("entry", &mut entry[..]), block("exit", &mut exit[..]),
        block("bridge", &mut bridge[..]), block("cycle", &mut cycle[..]),
        block("empty", &mut [])];
    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);
        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);
        }
    }
}

/// Local uses precede definitions, and block parameters define their registers.
@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {
    let parameter = il::Reg { n: 33 };
    let temporary = il::Reg { n: 66 };
    let external = il::Reg { n: 0 };

82	82		// Compute local defs and uses for each block.
83	83		for b in 0..blockCount {
84	84		let block = &func.blocks[b];
85	85		computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
86	86		}
	87	+	propagateLiveness(func.blocks, liveIn, liveOut, defs, uses, words);
	88	+	return LiveInfo 'scratch { liveIn: &liveIn[..], liveOut: &liveOut[..], defs: &defs[..], uses: &uses[..], words, blockCount, maxReg };
	89	+	}
	90	+
	91	+	/// Propagate successor uses until every block's live-in row is stable.
	92	+	fn propagateLiveness(
	93	+	blocks: &[il::Block],
	94	+	liveIn: &mut [u32],
	95	+	liveOut: &mut [u32],
	96	+	defs: &[u32],
	97	+	uses: &[u32],
	98	+	words: u32,
	99	+	) {
87	100		// Live sets grow monotonically from empty sets; no scratch set is needed.
88	101		let mut changed = true;
89	102
90	103		while changed {
91	104		set changed = false;
92	105
93	106		// Process blocks in reverse order (approximates post-order).
94		-	let mut b = blockCount;
	107	+	let mut b = blocks.len;
95	108		while b > 0 {
96	109		set b -= 1;
97		-	let block = &func.blocks[b];
	110	+	let block = &blocks[b];
98	111
99	112		// Add successor live-in sets directly to this block's live-out set.
100		-	addSuccessorLiveIn(block, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);
	113	+	unsafe {
	114	+	addSuccessorLiveIn(block, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);
	115	+	}
101	116
102	117		if computeAndUpdateLiveIn(&mut liveIn[b * words..(b + 1) * words], &liveOut[b * words..(b + 1) * words], &defs[b * words..(b + 1) * words], &uses[b * words..(b + 1) * words]) {
103	118		set changed = true;
104	119		}
105	120		}
106	121		}
107		-	return LiveInfo 'scratch { liveIn: &liveIn[..], liveOut: &liveOut[..], defs: &defs[..], uses: &uses[..], words, blockCount, maxReg };
108	122		}
109	123
110	124		/// Compute `liveIn = uses \| (liveOut - defs)` and update `dst`.
111	125		/// Returns `true` if `dst` changed. Combined loop avoids multiple passes.
112	126		fn computeAndUpdateLiveIn(

40	40		try check(super::liveOutRow(&live, 4), false, false, false);
41	41		}
42	42		}
43	43		}
44	44
	45	+	/// A cyclic graph propagates uses against block order until all rows stabilize.
	46	+	@test unsafe fn testDelayedCyclicPropagation() throws (testing::TestError) {
	47	+	let value = il::Reg { n: 66 };
	48	+	let mut entry = [il::Instr::Copy { dst: value, val: il::Val::Imm(7) },
	49	+	il::Instr::Jmp { target: 3, args: &mut [] }];
	50	+	let mut exit = [il::Instr::Ret { val: il::Val::Reg(value) }];
	51	+	let mut bridge = [il::Instr::Jmp { target: 1, args: &mut [] }];
	52	+	let mut cycle = [il::Instr::Br { op: il::CmpOp::Eq, typ: il::Type::W64,
	53	+	a: il::Val::Imm(0), b: il::Val::Imm(1), thenTarget: 3, thenArgs: &mut [],
	54	+	elseTarget: 2, elseArgs: &mut [] }];
	55	+	let blocks = [block("entry", &mut entry[..]), block("exit", &mut exit[..]),
	56	+	block("bridge", &mut bridge[..]), block("cycle", &mut cycle[..]),
	57	+	block("empty", &mut [])];
	58	+	let function = il::Fn { name: "cycle", params: &[], returnType: il::Type::W64,
	59	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	60	+	static DATA: [u8; 8192] = [0; 8192];
	61	+	let mut arena = alloc::new(&mut DATA[..]);
	62	+	use arena as analysis in {
	63	+	let live = try! super::analyze(&function, &analysis);
	64	+	for index in 0..blocks.len {
	65	+	try check(super::liveInRow(&live, index), false, false, index > 0 and index < 4);
	66	+	try check(super::liveOutRow(&live, index), false, false, index <> 1 and index < 4);
	67	+	}
	68	+	}
	69	+	}
	70	+
45	71		/// Local uses precede definitions, and block parameters define their registers.
46	72		@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {
47	73		let parameter = il::Reg { n: 33 };
48	74		let temporary = il::Reg { n: 66 };
49	75		let external = il::Reg { n: 0 };