radiance · commit

compiler: Borrow local liveness tables in checked code

5d3e041489d25636d3e27b32e6d29403fbae3af231153a7d8d32dd8ee5fc82f2

Alexis Sellier committed 6 days ago 1 parent 972c0b10

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

    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 {
        computeLocalDefsUses(&func.blocks[b], &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
        let block = &func.blocks[b];
        computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
    }
    // Live sets grow monotonically from empty sets; no scratch set is needed.
    let mut changed = true;

    while changed {

    }
    return changed;
}

/// Compute local defs and uses for a single block.
unsafe fn computeLocalDefsUses(block: &il::Block, defs: &mut [u32], uses: &mut [u32]) {
    for p in block.params {
fn computeLocalDefsUses(params: &[il::Param], instructions: &[il::Instr], defs: &mut [u32], uses: &mut [u32]) {
    for p in params {
        bitset::put(defs, p.value.n);
    }
    for instr in block.instrs {
        let mut registers = il::registers(&instr);
        while let reg = il::nextReg(&mut registers, &instr) {
            addUse(reg, defs, uses);
    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);
            }
        }

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


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

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

/// 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 };
    let params = [il::Param { value: parameter, type: il::Type::W64 }];
    let mut instructions = [
        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: temporary,
            a: il::Val::Reg(external), b: il::Val::Reg(parameter) },
        il::Instr::Copy { dst: external, val: il::Val::Reg(temporary) },
        il::Instr::Ret { val: il::Val::Reg(external) },
    ];
    let blocks = [il::Block { label: "entry", params: &params[..],
        instrs: &mut instructions[..], locs: &[], preds: &[], loopDepth: 0 },
        block("empty", &mut [])];
    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);
        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);
    }
}

/// 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 };

137	138		}
138	139		return changed;
139	140		}
140	141
141	142		/// Compute local defs and uses for a single block.
142		-	unsafe fn computeLocalDefsUses(block: &il::Block, defs: &mut [u32], uses: &mut [u32]) {
143		-	for p in block.params {
	143	+	fn computeLocalDefsUses(params: &[il::Param], instructions: &[il::Instr], defs: &mut [u32], uses: &mut [u32]) {
	144	+	for p in params {
144	145		bitset::put(defs, p.value.n);
145	146		}
146		-	for instr in block.instrs {
147		-	let mut registers = il::registers(&instr);
148		-	while let reg = il::nextReg(&mut registers, &instr) {
149		-	addUse(reg, defs, uses);
	147	+	for i in 0..instructions.len {
	148	+	let instr = &instructions[i];
	149	+	let mut registers = il::registers(instr);
	150	+	// Argument groups contain raw views into the function's IL storage.
	151	+	unsafe {
	152	+	while let reg = il::nextReg(&mut registers, instr) {
	153	+	addUse(reg, defs, uses);
	154	+	}
150	155		}
151	156
152		-	if let dst = il::instrDst(instr) {
	157	+	if let dst = il::instrDst(*instr) {
153	158		bitset::put(defs, dst.n);
154	159		}
155	160		}
156	161		}
157	162

92	92		let defs = try storage.fill(0 as u32, count);
93	93		let uses = try storage.fill(0 as u32, count);
94	94
95	95		// Compute local defs and uses for each block.
96	96		for b in 0..blockCount {
97		-	computeLocalDefsUses(&func.blocks[b], &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
	97	+	let block = &func.blocks[b];
	98	+	computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);
98	99		}
99	100		// Live sets grow monotonically from empty sets; no scratch set is needed.
100	101		let mut changed = true;
101	102
102	103		while changed {

40	40		try check(super::liveOutRow(&live, 4), false, false, false);
41	41		}
42	42		}
43	43		}
44	44
	45	+	/// Local uses precede definitions, and block parameters define their registers.
	46	+	@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {
	47	+	let parameter = il::Reg { n: 33 };
	48	+	let temporary = il::Reg { n: 66 };
	49	+	let external = il::Reg { n: 0 };
	50	+	let params = [il::Param { value: parameter, type: il::Type::W64 }];
	51	+	let mut instructions = [
	52	+	il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: temporary,
	53	+	a: il::Val::Reg(external), b: il::Val::Reg(parameter) },
	54	+	il::Instr::Copy { dst: external, val: il::Val::Reg(temporary) },
	55	+	il::Instr::Ret { val: il::Val::Reg(external) },
	56	+	];
	57	+	let blocks = [il::Block { label: "entry", params: &params[..],
	58	+	instrs: &mut instructions[..], locs: &[], preds: &[], loopDepth: 0 },
	59	+	block("empty", &mut [])];
	60	+	let function = il::Fn { name: "local", params: &[], returnType: il::Type::W64,
	61	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	62	+	static DATA: [u8; 8192] = [0; 8192];
	63	+	let mut arena = alloc::new(&mut DATA[..]);
	64	+	use arena as analysis in {
	65	+	let live = try! super::analyze(&function, &analysis);
	66	+	try check(&live.defs[..live.words], true, true, true);
	67	+	try check(&live.uses[..live.words], true, false, false);
	68	+	try check(super::liveInRow(&live, 0), true, false, false);
	69	+	try check(&live.defs[live.words..], false, false, false);
	70	+	try check(&live.uses[live.words..], false, false, false);
	71	+	}
	72	+	}
	73	+
45	74		/// Liveness sizes its rows from register operands and definitions.
46	75		@test unsafe fn testLargeRegisterExtent() throws (testing::TestError) {
47	76		for index in [8191 as u32, 8192, 8193, 16384] {
48	77		let source = il::Reg { n: index };
49	78		let destination = il::Reg { n: index + 1 };