radiance · commit

compiler: Check borrowed successor liveness merging

9ab18d59dedd0217cee358c0e8b5188ec580fb46273fa221ac1e23fe505c4706

Alexis Sellier committed 6 days ago 1 parent 09c34aea

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

        while b > 0 {
            set b -= 1;
            let block = &func.blocks[b];

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

        set *max = count;
    }
}

/// 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]) {
unsafe fn addSuccessorLiveIn(block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
    if block.instrs.len == 0 {
        return;
    }
    let term = block.instrs[block.instrs.len - 1];
    let term = &block.instrs[block.instrs.len - 1];
    if let case il::Instr::Switch { cases, .. } = term {
        mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);
    } else {
        mergeSuccessorLiveIn(term, &[], liveIn, words, liveOut);
    }
}

/// Merge live-in rows selected by a terminator and its borrowed switch cases.
fn mergeSuccessorLiveIn(term: &il::Instr, cases: &[il::SwitchCase], liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
    match term {
        case il::Instr::Jmp { target, .. } =>
            unionBlockLiveIn(target, liveIn, words, liveOut),
            unionBlockLiveIn(*target, liveIn, words, liveOut),
        case il::Instr::Br { thenTarget, elseTarget, .. } => {
            unionBlockLiveIn(thenTarget, liveIn, words, liveOut);
            unionBlockLiveIn(elseTarget, liveIn, words, liveOut);
            unionBlockLiveIn(*thenTarget, liveIn, words, liveOut);
            unionBlockLiveIn(*elseTarget, liveIn, words, liveOut);
        },
        case il::Instr::Switch { defaultTarget, cases, .. } => {
            unionBlockLiveIn(defaultTarget, liveIn, words, liveOut);
        case il::Instr::Switch { defaultTarget, .. } => {
            unionBlockLiveIn(*defaultTarget, liveIn, words, liveOut);
            for c in cases {
                unionBlockLiveIn(c.target, liveIn, words, liveOut);
            }
        },
        else => {},

lib/std/lang/gen/regalloc/liveness/tests.rad +29 -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 };
}

/// 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 [] },
            il::SwitchCase { value: 1, target: 1, args: &mut [] },
            il::SwitchCase { value: 2, target: 2, args: &mut [] },
        ];
        let mut entry = [il::Instr::Switch { val: il::Val::Imm(0),
            defaultTarget: 3, defaultArgs: &mut [], cases: &mut cases[..count] }];
        let mut first = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0 }) }];
        let mut second = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 33 }) }];
        let mut fallback = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];
        let blocks = [block("entry", &mut entry[..]), block("first", &mut first[..]),
            block("second", &mut second[..]), block("default", &mut fallback[..]),
            block("empty", &mut [])];
        let function = il::Fn { name: "switch", 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(super::liveOutRow(&live, 0), count > 0, count == 3, true);
            try check(super::liveInRow(&live, 0), count > 0, count == 3, true);
            try check(super::liveOutRow(&live, 4), 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 };

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

172	172		set *max = count;
173	173		}
174	174		}
175	175
176	176		/// Add successor live-in sets to the block's live-out set.
177		-	unsafe fn addSuccessorLiveIn(func: &il::Fn, block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
	177	+	unsafe fn addSuccessorLiveIn(block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
178	178		if block.instrs.len == 0 {
179	179		return;
180	180		}
181		-	let term = block.instrs[block.instrs.len - 1];
	181	+	let term = &block.instrs[block.instrs.len - 1];
	182	+	if let case il::Instr::Switch { cases, .. } = term {
	183	+	mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);
	184	+	} else {
	185	+	mergeSuccessorLiveIn(term, &[], liveIn, words, liveOut);
	186	+	}
	187	+	}
182	188
	189	+	/// Merge live-in rows selected by a terminator and its borrowed switch cases.
	190	+	fn mergeSuccessorLiveIn(term: &il::Instr, cases: &[il::SwitchCase], liveIn: &[u32], words: u32, liveOut: &mut [u32]) {
183	191		match term {
184	192		case il::Instr::Jmp { target, .. } =>
185		-	unionBlockLiveIn(target, liveIn, words, liveOut),
	193	+	unionBlockLiveIn(*target, liveIn, words, liveOut),
186	194		case il::Instr::Br { thenTarget, elseTarget, .. } => {
187		-	unionBlockLiveIn(thenTarget, liveIn, words, liveOut);
188		-	unionBlockLiveIn(elseTarget, liveIn, words, liveOut);
	195	+	unionBlockLiveIn(*thenTarget, liveIn, words, liveOut);
	196	+	unionBlockLiveIn(*elseTarget, liveIn, words, liveOut);
189	197		},
190		-	case il::Instr::Switch { defaultTarget, cases, .. } => {
191		-	unionBlockLiveIn(defaultTarget, liveIn, words, liveOut);
	198	+	case il::Instr::Switch { defaultTarget, .. } => {
	199	+	unionBlockLiveIn(*defaultTarget, liveIn, words, liveOut);
192	200		for c in cases {
193	201		unionBlockLiveIn(c.target, liveIn, words, liveOut);
194	202		}
195	203		},
196	204		else => {},

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	+	/// Switch successors merge distinct words and tolerate repeated destinations.
	17	+	@test unsafe fn testSwitchSuccessorLiveness() throws (testing::TestError) {
	18	+	for count in [0 as u32, 1, 3] {
	19	+	let mut cases = [
	20	+	il::SwitchCase { value: 0, target: 1, args: &mut [] },
	21	+	il::SwitchCase { value: 1, target: 1, args: &mut [] },
	22	+	il::SwitchCase { value: 2, target: 2, args: &mut [] },
	23	+	];
	24	+	let mut entry = [il::Instr::Switch { val: il::Val::Imm(0),
	25	+	defaultTarget: 3, defaultArgs: &mut [], cases: &mut cases[..count] }];
	26	+	let mut first = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0 }) }];
	27	+	let mut second = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 33 }) }];
	28	+	let mut fallback = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];
	29	+	let blocks = [block("entry", &mut entry[..]), block("first", &mut first[..]),
	30	+	block("second", &mut second[..]), block("default", &mut fallback[..]),
	31	+	block("empty", &mut [])];
	32	+	let function = il::Fn { name: "switch", params: &[], returnType: il::Type::W64,
	33	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	34	+	static DATA: [u8; 8192] = [0; 8192];
	35	+	let mut arena = alloc::new(&mut DATA[..]);
	36	+	use arena as analysis in {
	37	+	let live = try! super::analyze(&function, &analysis);
	38	+	try check(super::liveOutRow(&live, 0), count > 0, count == 3, true);
	39	+	try check(super::liveInRow(&live, 0), count > 0, count == 3, true);
	40	+	try check(super::liveOutRow(&live, 4), false, false, false);
	41	+	}
	42	+	}
	43	+	}
	44	+
16	45		/// Liveness sizes its rows from register operands and definitions.
17	46		@test unsafe fn testLargeRegisterExtent() throws (testing::TestError) {
18	47		for index in [8191 as u32, 8192, 8193, 16384] {
19	48		let source = il::Reg { n: index };
20	49		let destination = il::Reg { n: index + 1 };