radiance · commit

compiler: Borrow instruction tables for liveness queries

989da8bfe2b41499682bcca41ca64ad7c46b1f80a384934368f9e6697b399e60

Alexis Sellier committed 6 days ago 1 parent 1671d5e0

lib/std/lang/gen/regalloc/liveness.rad +20 -17

            set b -= 1;
            let block = &blocks[b];

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

        set *max = count;
    }
}

/// Add successor live-in sets to the block's live-out set.
unsafe fn addSuccessorLiveIn(block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
    if block.instrs.len == 0 {
fn addSuccessorLiveIn(instructions: &[il::Instr], liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
    if instructions.len == 0 {
        return;
    }
    let term = &block.instrs[block.instrs.len - 1];
    let term = &instructions[instructions.len - 1];
    if let case il::Instr::Switch { cases, .. } = term {
        mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);
        unsafe {
            mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);
        }
    } else {
        mergeSuccessorLiveIn(term, &[], liveIn, words, liveOut);
    }
}


    let block = &func.blocks[blockIdx];

    if bitset::contains(liveOutRow(info, blockIdx), reg.n) {
        return true;
    }
    for i in (instrIdx + 1)..block.instrs.len {
        if instrUsesReg(block.instrs[i], reg) {
            return true;
        }
    }
    return false;
    return usesRegisterAfter(block.instrs, instrIdx, reg);
}

/// Check if an instruction uses a specific register.
unsafe fn instrUsesReg(instr: il::Instr, reg: il::Reg) -> bool {
    let mut registers = il::registers(&instr);
    while let source = il::nextReg(&mut registers, &instr) {
        if source.n == reg.n {
            return true;
/// Check if an instruction after the given index uses a specific register.
fn usesRegisterAfter(instructions: &[il::Instr], instrIdx: u32, reg: il::Reg) -> bool {
    for i in (instrIdx + 1)..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 source = il::nextReg(&mut registers, instr) {
                if source.n == reg.n {
                    return true;
                }
            }
        }
    }
    return false;
}


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

            try check(super::liveOutRow(&live, index), false, false, index <> 1 and index < 4);
        }
    }
}

/// Later-use queries include outgoing values and exclude the current instruction.
@test unsafe fn testLaterUses() throws (testing::TestError) {
    let outgoing = il::Reg { n: 0 };
    let argument = il::Reg { n: 1 };
    let result = il::Reg { n: 33 };
    let unused = il::Reg { n: 66 };
    let params = [il::Param { value: argument, type: il::Type::W64 }];
    let args = [il::Val::Imm(0), il::Val::Reg(argument), il::Val::Reg(argument)];
    let mut entry = [
        il::Instr::Copy { dst: outgoing, val: il::Val::Imm(1) },
        il::Instr::Call { retTy: il::Type::W64, dst: result,
            func: il::Val::FnAddr("callee"), args: &args[..] },
        il::Instr::Copy { dst: unused, val: il::Val::Reg(result) },
        il::Instr::Jmp { target: 1, args: &mut [] },
    ];
    let mut exit = [il::Instr::Ret { val: il::Val::Reg(outgoing) }];
    let blocks = [block("entry", &mut entry[..]), block("exit", &mut exit[..])];
    let function = il::Fn { name: "later", params: &params[..], returnType: il::Type::W64,
        isExtern: false, isLeaf: false, 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..entry.len {
            assert super::hasLaterUse(&live, &function, 0, index, outgoing);
            assert super::hasLaterUse(&live, &function, 0, index, argument) == (index == 0);
            assert super::hasLaterUse(&live, &function, 0, index, result) == (index < 2);
            assert not super::hasLaterUse(&live, &function, 0, index, unused);
        }
        assert not super::hasLaterUse(&live, &function, 1, 0, outgoing);
    }
}

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

109	109		set b -= 1;
110	110		let block = &blocks[b];
111	111
112	112		// Add successor live-in sets directly to this block's live-out set.
113	113		unsafe {
114		-	addSuccessorLiveIn(block, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);
	114	+	addSuccessorLiveIn(block.instrs, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);
115	115		}
116	116
117	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]) {
118	118		set changed = true;
119	119		}

198	198		set *max = count;
199	199		}
200	200		}
201	201
202	202		/// Add successor live-in sets to the block's live-out set.
203		-	unsafe fn addSuccessorLiveIn(block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
204		-	if block.instrs.len == 0 {
	203	+	fn addSuccessorLiveIn(instructions: &[il::Instr], liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
	204	+	if instructions.len == 0 {
205	205		return;
206	206		}
207		-	let term = &block.instrs[block.instrs.len - 1];
	207	+	let term = &instructions[instructions.len - 1];
208	208		if let case il::Instr::Switch { cases, .. } = term {
209		-	mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);
	209	+	unsafe {
	210	+	mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);
	211	+	}
210	212		} else {
211	213		mergeSuccessorLiveIn(term, &[], liveIn, words, liveOut);
212	214		}
213	215		}
214	216

241	243		let block = &func.blocks[blockIdx];
242	244
243	245		if bitset::contains(liveOutRow(info, blockIdx), reg.n) {
244	246		return true;
245	247		}
246		-	for i in (instrIdx + 1)..block.instrs.len {
247		-	if instrUsesReg(block.instrs[i], reg) {
248		-	return true;
249		-	}
250		-	}
251		-	return false;
	248	+	return usesRegisterAfter(block.instrs, instrIdx, reg);
252	249		}
253	250
254		-	/// Check if an instruction uses a specific register.
255		-	unsafe fn instrUsesReg(instr: il::Instr, reg: il::Reg) -> bool {
256		-	let mut registers = il::registers(&instr);
257		-	while let source = il::nextReg(&mut registers, &instr) {
258		-	if source.n == reg.n {
259		-	return true;
	251	+	/// Check if an instruction after the given index uses a specific register.
	252	+	fn usesRegisterAfter(instructions: &[il::Instr], instrIdx: u32, reg: il::Reg) -> bool {
	253	+	for i in (instrIdx + 1)..instructions.len {
	254	+	let instr = &instructions[i];
	255	+	let mut registers = il::registers(instr);
	256	+	// Argument groups contain raw views into the function's IL storage.
	257	+	unsafe {
	258	+	while let source = il::nextReg(&mut registers, instr) {
	259	+	if source.n == reg.n {
	260	+	return true;
	261	+	}
	262	+	}
260	263		}
261	264		}
262	265		return false;
263	266		}
264	267

66	66		try check(super::liveOutRow(&live, index), false, false, index <> 1 and index < 4);
67	67		}
68	68		}
69	69		}
70	70
	71	+	/// Later-use queries include outgoing values and exclude the current instruction.
	72	+	@test unsafe fn testLaterUses() throws (testing::TestError) {
	73	+	let outgoing = il::Reg { n: 0 };
	74	+	let argument = il::Reg { n: 1 };
	75	+	let result = il::Reg { n: 33 };
	76	+	let unused = il::Reg { n: 66 };
	77	+	let params = [il::Param { value: argument, type: il::Type::W64 }];
	78	+	let args = [il::Val::Imm(0), il::Val::Reg(argument), il::Val::Reg(argument)];
	79	+	let mut entry = [
	80	+	il::Instr::Copy { dst: outgoing, val: il::Val::Imm(1) },
	81	+	il::Instr::Call { retTy: il::Type::W64, dst: result,
	82	+	func: il::Val::FnAddr("callee"), args: &args[..] },
	83	+	il::Instr::Copy { dst: unused, val: il::Val::Reg(result) },
	84	+	il::Instr::Jmp { target: 1, args: &mut [] },
	85	+	];
	86	+	let mut exit = [il::Instr::Ret { val: il::Val::Reg(outgoing) }];
	87	+	let blocks = [block("entry", &mut entry[..]), block("exit", &mut exit[..])];
	88	+	let function = il::Fn { name: "later", params: &params[..], returnType: il::Type::W64,
	89	+	isExtern: false, isLeaf: false, blocks: &blocks[..] };
	90	+	static DATA: [u8; 8192] = [0; 8192];
	91	+	let mut arena = alloc::new(&mut DATA[..]);
	92	+	use arena as analysis in {
	93	+	let live = try! super::analyze(&function, &analysis);
	94	+	for index in 0..entry.len {
	95	+	assert super::hasLaterUse(&live, &function, 0, index, outgoing);
	96	+	assert super::hasLaterUse(&live, &function, 0, index, argument) == (index == 0);
	97	+	assert super::hasLaterUse(&live, &function, 0, index, result) == (index < 2);
	98	+	assert not super::hasLaterUse(&live, &function, 0, index, unused);
	99	+	}
	100	+	assert not super::hasLaterUse(&live, &function, 1, 0, outgoing);
	101	+	}
	102	+	}
	103	+
71	104		/// Local uses precede definitions, and block parameters define their registers.
72	105		@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {
73	106		let parameter = il::Reg { n: 33 };
74	107		let temporary = il::Reg { n: 66 };
75	108		let external = il::Reg { n: 0 };